P003 Longest Substring Without Repeating Characters

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

Examples:

1
2
3
4
5
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.

思路分析

  • 记录子串的起点(start)和终点(end)
  • 每次循环都将字符放入map中并记录其index
  • 当有重复的时(map中contains该字符)，更新start
  • 不重复时，取 max(start-end+1,ret)更新可能的最大值

代码

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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