LC3　无重复字符的最长子串¶

中等通过率 42.8%python3核心代码模式滑动窗口样例通过牛客 AC哈希表字符串滑动窗口

一句话

滑动窗口配一张「字符 -> 最后出现位置」的哈希表。

解题思路¶

这题考什么¶

要找最长的、字符互不相同的连续子串。枚举左右端点再判重是 O(n^2) 甚至 O(n^3)。

能上滑动窗口，靠的是一条单调性：若窗口 s[l .. r] 内部无重复，则它的任何子区间也无重复；反过来，一旦 r 右移引入了一个已在窗口里的字符，合法的左端点只可能变大，绝不会变小。于是 l 与 r 各自单调前进，整体一趟扫完。见双指针与滑动窗口。

左界为什么不能回退，说透一点：设当前窗口右端为 r，记 f(r) = 使 s[l .. r] 无重复的最小 l。f 是单调不减的—— 因为 s[f(r) .. r] 无重复，把右端从 r 扩到 r+1 只会增加约束，绝不会让更小的左端变得合法。左界一旦右移就是永久的，这正是「每个下标只被左右指针各碰一次」从而 O(n) 的根据。若允许 l 回退，窗口里会重新混进重复字符，答案会算大，复杂度也退化。

实现上用字典 last 记录每个字符最近一次出现的下标，右端 r 从 0 扫到 n-1：

若 s[r] 在 last 中，且 last[s[r]] >= l
    说明这个字符就落在当前窗口内 -> 把 l 直接跳到 last[s[r]] + 1
last[s[r]] = r
ans = max(ans, r - l + 1)

左界一步跳到重复字符的下一格，而不是逐格右移：中间那些位置作为左端点时，窗口里必然还含着那个重复字符，一个都不可能成立，可以整段跳过。

数据规模与复杂度¶

0 <= len(s) <= 1e5，字符是英文字母、数字、符号和空格。时间 O(n)：l 与 r 各自最多前进 n 步；空间 O(k)，k 是出现过的不同字符数，受字符集大小限制（本题的可见 ASCII 约一百多种），实际是常数级。枚举左右端点是 n 的平方除以二 = 5e9 次，Python 下差好几个数量级。

坑在哪¶

last[c] >= left 这个判断不能省，它是整题唯一的陷阱。字典里存的是全局最后一次出现的位置，很可能是早已被窗口甩在身后的旧记录。不比较就无脑把左界拉过去，left 会往回退，窗口里重新混进重复字符，长度也会算大。加上这个判断，left 全程单调不减。
last[c] 的更新必须在收缩左界之后。先写 last[c] = r 再判断，比较的就成了刚写进去的 r 与 left，条件永远成立，左界会被一路推到 r+1，答案退化成 1。
窗口长度是 right - left + 1（闭区间两端都算），少了这个 +1 每个答案都短一格。
空串要返回 0。这里靠 ans 的初值兜住：循环一次都不进，直接返回 0，不必特判。
严格比对：答案是一个整数。题面说 "abcabcbb" 的 "bca" "cab" 也是正确答案，指的是最长子串本身不唯一，但要返回的只是长度 3，仍然唯一。

样例复核¶

s = "pwwkew"，期望 3。

r=0 'p'  last 无 'p'                left=0  窗口 "p"    len=1
r=1 'w'  last 无 'w'                left=0  窗口 "pw"   len=2
r=2 'w'  last['w']=1 >= 0 -> left=2 窗口 "w"            len=1
r=3 'k'  last 无 'k'                left=2  窗口 "wk"   len=2
r=4 'e'  last 无 'e'                left=2  窗口 "wke"  len=3   <- 答案
r=5 'w'  last['w']=2 >= 2 -> left=3 窗口 "kew"          len=3

最长 3，与样例一致。r=5 那一步正是判断的价值所在：last['w'] = 2 仍在窗口内，必须收；若左界此刻已在 3 之后，那条记录就是过期的，照它跳反而会往回退。

参考实现¶

solutions/leetcode/LC3/sol.py
from typing import List, Optional


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}          # 字符 -> 它最后一次出现的下标（全局记录，未必还在窗口内）
        left = 0           # 窗口左端，闭区间；循环不变量：s[left..right] 内部无重复字符
        ans = 0            # 空串时循环不进入，直接返回 0
        for right, ch in enumerate(s):
            # 只有旧位置仍落在窗口内才需要收缩左界。否则那是早已滑出窗口的过期记录，
            # 照它跳会把左界往回拉——左界一旦回退，窗口里会重新混进重复字符，
            # 长度也会算大。有了这个比较，left 全程单调不减
            if ch in last and last[ch] >= left:
                left = last[ch] + 1     # 一步跳到重复字符的下一格：中间的左端点都不可能合法
            last[ch] = right            # 必须在收缩之后更新，否则比较的是刚写进去的自己
            # 窗口是闭区间，长度为 right - left + 1
            if right - left + 1 > ans:
                ans = right - left + 1
        return ans

LC3 无重复字符的最长子串¶