3. Longest Substring Without Repeating Characters

2019-03-28

3. Longest Substring Without Repeating Characters

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

Example 1:

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

Example 2:

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

Example 3:

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class solution:
# @param {string} s
# @return {integer}
def lengthOfLongestSubstring(self, s):
    # substring开始节点和最长substring设为0
    start = len_max = 0
    # dictionary存储已经出现过的char，和其最近出现位置
    char_dict = {}
    # 开始遍历
    for i in range(len(s)):
        # s[i]在字典中出现过，并且子串起始位置在最近这个字符出现位置之前或一致，此时为重复字符
        if s[i] in char_dict and start <= char_dict[s[i]]:
            #该重复字符出现位置后设为新子串起始位置
            start = char_dict[s[i]] + 1
        # 字典中未出现过的新字符，或者新子串中未出现过的字符，为子串中字符
        else:
            # 实时比较至该字符为止的新子串，与之前最长子串长度对比
            len_max = max(len_max, i - start + 1)
        # 实时更新dict中s[i]的最新位置
        char_dict[s[i]] = i
    return len_max

Input: pwwkew

1
2
3
4
5
6
7
# i=0时 s[0]=p ->len_max =1 char_dict[p]=0
# i=1时 s[1]=w ->len_max =2 char_dict[w]=1
# i=2时 s[2]=w start=2 ->char_dict[2]=2
# i=3时 s[3]=k ->len_max =2 char_dict[k]=3
# i=4时 s[4]=e ->len_max =3 char_dict[e]=4
# i=5时 s[5]=w start=3 ->char_dict[w]=5
# len_max =3

##

##

-->