[LeetCode] 3.Longest Substring Without Repeating Characters 最长无重复子串

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

滑动窗口法,右指针从左往右扫描字符串,遇到没出现过的字符就直接记录,当扫到的字符出现过,左指针一直向右走,直到遇到重复字符时,左指针在右移1位。比较当前不重复字符串长度与max值,更新max值。最后返回max值。

字符的记录可用hashmap或int[256], 记录和查寻字符的方式有两种:

第一种记录每个字符上次出现的位置,当遇到新字符时,直接记录字符位置。当遇到的字符存在时,如果记录的位置小于左指针的位置,说明被跳过了,重新记录当前位置。当遇到重复的字符存在并且在左指针右边(在窗口内)时,指针直接跳到记录的这个字符上次出现的位置加1,就是跳过这个字符,然后记录这个新的位置。

第二种记录字符是否出现,如果扫到重复的字符,左指针向右移动,到重复字符的位置加1,这之间扫过的字符都删掉,因为不在窗口里了。

Java:

  public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}  

Java: HashMap

public class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<Character,Integer>();
int maxLen = 0;
int start = 0;
for (int i = 0; i< s.length(); i++) {
if (!map.containsKey(s.charAt(i)) || map.get(s.charAt(i)) < start) {
map.put(s.charAt(i),i);
}
else {
maxLen = Math.max(maxLen,i - start);
start = map.get(s.charAt(i)) + 1;
map.put(s.charAt(i),i);
}
} maxLen = Math.max(maxLen, s.length() - start); return maxLen;
}
}

Java 2: HashSet

class Solution {
public int lengthOfLongestSubstring(String s) {
int longest = 0;
int i = 0;
Set<Character> set = new HashSet<>(); for (int j = 0; j < s.length(); j++) {
while (set.contains(s.charAt(j))) {
set.remove(s.charAt(i));
i++;
} set.add(s.charAt(j));
longest = Math.max(longest, j - i + 1);
}
return longest;
}
}

Java 3: boolean[256]

public class Solution {
public int lengthOfLongestSubstring(String s) {
boolean[] visited = new boolean[256];
int start = 0, last = 0, max = 0, length = s.length();
while(last < length) {
if(!visited[s.charAt(last)]) {
visited[s.charAt(last)] = true;
max = Math.max(max, last++ - start + 1);
} else {
while(visited[s.charAt(last)])
visited[s.charAt(start++)] = false;
visited[s.charAt(last++)] = true;
}
}
return max;
}
}

Java 4: int[256]

public class Solution {
public int lengthOfLongestSubstring(String s) {
int[] m = new int[256];
Arrays.fill(m, -1);
int res = 0, left = -1;
for (int i = 0; i < s.length(); ++i) {
left = Math.max(left, m[s.charAt(i)]);
m[s.charAt(i)] = i;
res = Math.max(res, i - left);
}
return res;
}
}

Python:

class Solution2(object):
def lengthOfLongestSubstring(self, s):
a={}
count=0
first=-1
for i in range(len(s)):
if s[i] in a and a[s[i]]>first:
first=a[s[i]]
a[s[i]]=i
count=max(count,(i-first))
return count

Python:

class Solution(object):
def lengthOfLongestSubstring(self, s):
a=[-1]*256
count=0
first=-1
for i in range(len(s)):
if a[ord(s[i])]>first:
first=a[ord(s[i])]
a[ord(s[i])]=i
count=max(count,(i-first))
return count

Python:

class Solution:
def lengthOfLongestSubstring(self, s):
longest, start, visited = 0, 0, [False for _ in xrange(256)]
for i, char in enumerate(s):
if visited[ord(char)]:
while char != s[start]:
visited[ord(s[start])] = False
start += 1
start += 1
else:
visited[ord(char)] = True
longest = max(longest, i - start + 1)
return longest

Python: wo

class Solution():
def longestSubstring(self, s):
longest, lookup = 0, {}
for k, v in enumerate(s):
if v not in lookup:
lookup[v] = k
longest = max(longest, len(lookup))
else:
for j in range(lookup[v], k):
lookup.pop(s[j]) return longest  

Python: wo

class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start, mx, m = 0, 0, {}
for i in xrange(len(s)):
if s[i] in m and m[s[i]] >= start:
start = m[s[i]] + 1
m[s[i]] = i
mx = max(mx, i - start + 1) return mx 

C++:

class Solution {
public:
int lengthOfLongestSubstring(string s) {
int m[256] = {0}, res = 0, left = 0;
for (int i = 0; i < s.size(); ++i) {
if (m[s[i]] == 0 || m[s[i]] < left) {
res = max(res, i - left + 1);
} else {
left = m[s[i]];
}
m[s[i]] = i + 1;
}
return res;
}
}; 

C++:

class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> m(256, -1);
int res = 0, left = -1;
for (int i = 0; i < s.size(); ++i) {
left = max(left, m[s[i]]);
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};

    

类似题目:

[LeetCode] 76. Minimum Window Substring 最小窗口子串

[LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串

[LeetCode] 340. Longest Substring with At Most K Distinct Characters 最多有K个不同字符的最长子串

[LeetCode] 727. Minimum Window Subsequence 最小窗口子序列  

All LeetCode Questions List 题目汇总

 

上一篇:【Java每日一题】20170329


下一篇:wordpress自定义后台用户联系方式 添加qq、微博、微信