[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 题目汇总