3. 无重复字符的最长子串

LeetCode 3¹ · 中等 · 滑动窗口

题

给一个字符串，求其中不含重复字符的最长连续子串的长度。

例："abcabcbb" → 3（"abc"）；"pwwkew" → 3（"wke"，"pwke" 不连续不算）。

一句话

窗口 [l, r] 始终无重复；右端每进一个字符，若它上次出现在窗口里，左端直接跳到那次出现的下一位。

关键技巧

为什么能用滑窗：性质对子串「单调」。 一个子串无重复，它的所有子串也无重复；一个子串有重复，包含它的所有串也有重复。于是对每个右端点 r，合法左端点是一段连续区间 [L(r), r]，而且 L(r) 随 r 单调不减——左指针永远不用回头，两指针各走 \(n\) 步。

记「最后出现位置」让左端一次跳到位。 用 last[c] 存字符 c 最后出现的下标。新字符 c 进窗口时：

• 若 last[c] >= l，说明它在窗口里，把 l 设为 last[c] + 1；
• 若 last[c] < l，它在窗口外，是早已失效的旧记录，不动 l。

第二条是常见坑。 写成 l = last[c] + 1 不加判断，会让左端往回跳——比如 "abba" 在最后一个 a 时会把 l 从 2 拉回 1。等价写法是 l = max(l, last[c] + 1)。

解

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}
        l = best = 0
        for r, c in enumerate(s):
            if last.get(c, -1) >= l:
                l = last[c] + 1
            last[c] = r
            best = max(best, r - l + 1)
        return best

时间 \(O(n)\)，空间 \(O(|\Sigma|)\)，\(\Sigma\) 为字符集。

延伸

• 可变长窗口的通用模板：「右端扩一格 → while 不合法就收左端 → 更新答案」。求最短合法窗口的版本见 76. 最小覆盖子串。
• 定长窗口版本见 438. 找到字符串中所有字母异位词。
• 变体「最多包含 k 种不同字符的最长子串」：窗口内维护计数和种类数，种类数 > k 时收左端——同一模板，只是不能跳、只能一步步挪。

s = Solution()
assert s.lengthOfLongestSubstring("abcabcbb") == 3
assert s.lengthOfLongestSubstring("bbbbb") == 1
assert s.lengthOfLongestSubstring("pwwkew") == 3
assert s.lengthOfLongestSubstring("") == 0
assert s.lengthOfLongestSubstring("abba") == 2
assert s.lengthOfLongestSubstring(" ") == 1