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.

解法

思路：滑动窗口法

"pwwkew"
1   p           {p:0}              max=1       start=0
2   pw          {p:0,w:1}          max=2       start=0
3   pww         {p:0,w:2}          max=2       start=3
4   pwwk        {p:0,w:2,k:3}      max=2       start=3
5   pwwke       {p:0,w:2,k:3,e:4}  max=3       start=3
6   pwwkew      {p:0,w:5,k:3,e:4}  max=3       end

从第三行开始出现了第一个重复的字符w，此时start的位置为初始位置0，这是状态发生转移的条件：字符出现重复，并且重复字符出现的位置i大于start，这就意味着在s[start:i]之间出现了重复的字符，此时只需要将start移动到w上次出现的位置之后就行了。转换成程序语言就是：

# c is 'w'
if c in last_seen and last_seen[c] >= start:
    start = last_seen[c] + 1

状态发生变化的时候，子串的长度一定不会大于最大长度，因此该次不需要比较。因为遍历时指针每次只向前移动一个字符，而发生状态转移时至少会移动一个字符（例如从5到6，start正好位于w上一次出现的位置），这就意味着，状态转移时得到的新子串一定不会比上一次长。

如果没有发生状态转移，那么遍历会使当前子串长度加一，要统计更新后的最长字符串长度。

longest = max((i - start + 1), longest)

在每次遍历后更新字典，记录字符出现位置：

last_seen[c] = i

完整代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        start = 0
        longest = 0

        for i, c in enumerate(s):
            if c in last_seen and last_seen[c] >= start:
                # repeating words show in s[start: i],
                # so update start. start move forward
                # one step from last seen c, then we
                # can assure that from the start to i,
                # there is no repeated character.
                start = last_seen[c] + 1  
            else:
                # c is not in last_seen or c is ahead of start,
                # which means from start to i there is no repeating characters
                longest = max(longest, i - start + 1)
            last_seen[c] = i

        return longest

感觉还是没有写清楚，思路还是不够清晰。