无重复字符的最长子串

窗口表示什么

让 [left, right] 始终表示一个没有重复字符的子串。右边界负责探索新字符，出现冲突时，左边界负责恢复窗口的合法性。

def lengthOfLongestSubstring(s: str) -> int:
    last_seen = {}
    left = 0
    answer = 0

    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1

        last_seen[char] = right
        answer = max(answer, right - left + 1)

    return answer

最容易错的地方

更新左边界时必须判断旧位置是否还在当前窗口中。否则，遇到 abba 时，最后一个 a 会让左边界错误地向后退。

if char in last_seen and last_seen[char] >= left:
    left = last_seen[char] + 1

滑动窗口识别信号

• 答案来自连续区间；
• 右边界扩张后可以快速判断是否合法；
• 左边界右移能够恢复合法性；
• 两个边界都不会向后退，因此总移动次数是线性的。

这道题的时间复杂度是 $O(n)$，额外空间取决于字符集大小。