3. Longest Substring Without Repeating Characters

yPhantom 2019年10月14日 38次浏览

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.

Solution

通过维护一个dict,记录给出的字符串中的所有字符的下标,在遍历字符串的过程中,每处理一个字符的时候:

  • 字符是否已经在dict中,如果在,说明重复了,下一轮计算的start为当前位置+1
  • 字符不在dict中,则更新dict,并更新最大长度。
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        str_dict = {}
        start = 0
        max_len = 0
        for index, s in enumerate(s):
            if s in str_dict:
                start = max(str_dict[s] + 1, start)
            str_dict[s] = index
            max_len = max(max_len, index - start + 1)
        return max_len

start = max(str_dict[s] + 1, start)是针对例如tmmzuxta这种有多个字符重复的情况,在判断第二个t的时候,因为一开始维护的dict记录的t的下标为0,但是被废弃了,我们需要的是最右边的下标。