[TOC]
P003 Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
思路分析
- 記錄子串的起點(diǎn)(start)和終點(diǎn)(end)
- 每次循環(huán)都將字符放入map中并記錄其index
- 當(dāng)有重復(fù)的時(shí)(map中contains該字符)苛坚，更新start
- 不重復(fù)時(shí)叙甸，取 max(start-end+1,ret)更新可能的最大值
代碼
java
public int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s))
return 0;
Map<Character, Integer> map = new HashMap<>();
int ret = 0;
int start = 0, end = 0;
char[] arr = s.toCharArray();
while (end < arr.length) {
// map.get(arr[end]) >= start表示get到的char不能在start之前
if (map.containsKey(arr[end]) && map.get(arr[end]) >= start) {
start = map.get(arr[end]) + 1;
} else {
ret = Math.max(ret, end - start + 1);
}
map.put(arr[end], end);
end++;
}
return ret;
}
python
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s :return 0;
m = {}
ret = 0;start = 0;end = 0
while(end < len(s)):
if (s[end] in m) and (m[s[end]] >= start):
start = m[s[end]] + 1
else:
ret = max([ret, end - start + 1])
m[s[end]] = end
end += 1
# end while
return ret
