跳转至

LC76　最小覆盖子串

困难通过率 49.5%python3核心代码模式子串样例通过牛客 AC哈希表字符串滑动窗口

牛客原题 　源码

讲解章节：双指针与滑动窗口

一句话

可变长滑动窗口：右端负责凑齐，左端负责在合法前提下尽量压缩。

解题思路

这题考什么

要在 s 里找最短的、把 t 的每个字符（含重复次数）都覆盖住的子串。 枚举左右端点是 O(m^2) 个区间，每个还要验证一次覆盖，m = 1e5 下不可能。

能上滑动窗口的根据是单调性：若窗口 s[l .. r] 已经覆盖了 t， 那么把右端继续右扩得到的窗口也一定覆盖 t（字符只增不减）。 于是对每个右端 r，存在唯一的「最靠右的合法左端」g(r)， 而且 g 随 r 单调不减——右端右移只会让约束更松，合法左端不可能变得更靠左。 所以左指针只需单调右移、永不回退，两个指针合起来走 2m 步。 见 双指针与滑动窗口。

算法形态是「右端扩张到合法，左端收缩到临界，记录答案」：

右端每吞进一个字符 -> 更新计数
while 窗口已覆盖 t：
    用当前窗口长度更新答案
    左端吐出一个字符，左指针右移      （吐到不再覆盖为止）

覆盖判定怎么做到 O(1)：维护 

need[c]   还差多少个 c 才够（可以为负，负数表示窗口里多带了几个 c）
missing   还差多少个字符总数（把所有正的 need 加起来）

右端吞进 c 时，只有 need[c] > 0 才说明这个 c 是「真正补上缺口」的， 此时 missing 减一；否则它只是多余的富余量。missing == 0 就是覆盖成立。 用一个标量代替「逐个检查 t 里每种字符够不够」，把每步压成常数。

数据规模与复杂度

1 <= m = len(s), n = len(t) <= 1e5，s 与 t 都由英文字母组成 （大小写都算，共 52 种，所以用字典而不是长度 26 的数组）。 时间 O(m + n)：建 need 表 O(n)，左右指针各自单调走完 s 一遍； 空间 O(k)，k 是 t 里的不同字符数，上界 52，实际是常数。 正好达到题面「进阶」要求的 O(m + n)。

坑在哪

  1. 左指针不能回退，这是整份解法的效率根据，也是最容易写错的地方。 常见的错误写法是「右端每前进一步，就从头再找一次最优左端」， 那是 O(m^2)。左端只右移的合法性来自上面那条单调性： r 增大时最靠右的合法左端 g(r) 不会变小，所以走过的位置永远不必回头。
  2. t 里有重复字符时必须按次数统计，不能退化成集合。 题面明示「包括重复字符」，示例 3 的 s = "a"、t = "aa" 期望空串， 若把 t 当成集合，会误判 "a" 已覆盖。
  3. need[c] 允许为负，这不是 bug 而是设计：负值记录窗口里多带的富余量。 正因如此，左端吐出字符时要先加回 need[c]，再看它是否变成正数—— 只有从 0 变成 1 才意味着真的缺了，missing 才加一。 若只要 need[c] 不为 0 就加 missing，富余字符会被误判成缺口， 窗口刚一收缩就退出，答案偏长。
  4. 记录答案要在收缩循环内部、吐出字符之前。放到循环外面， 记下的是已经不再覆盖的窗口，长度会短一格且不合法。
  5. 窗口长度是 right - left + 1（闭区间），最终切片是 s[best_l : best_l + best_len]， 切片右端是开区间，写成 s[best_l : best_l + best_len - 1] 会少一个字符。
  6. 无解时返回空字符串。这里靠 best_len 的初值（比 m 大的哨兵）兜住： 从没进过收缩循环则 best_len 不变，直接返回 ""。若初值取 0 之类的值， 就分不清「无解」与「找到了长度 0 的答案」。
  7. 严格比对：题面写「测试用例保证答案唯一」，所以最短覆盖子串就是那一个， 不存在多解放宽。

样例复核

s = "ADOBECODEBANC"，t = "ABC"，need = A:1 B:1 C:1，missing = 3。 

下标      0 1 2 3 4 5 6 7 8 9 10 11 12
字符      A D O B E C O D E B  A  N  C
r=0  'A'  need[A] 由 1 减到 0，missing=2
r=3  'B'  missing=1
r=5  'C'  missing=0，覆盖成立，进入收缩：
          窗口 [0,5] "ADOBEC" 长 6 -> 记为当前最优；
          吐 s[0]='A'，need[A] 回到 1（真的缺了），missing=1，left=1，退出
r=9  'B'  need[B] 此刻是 0，不是正数 -> missing 不变（仍是 1），
          need[B] 变成 -1，记下「窗口里多带了一个 B」
r=10 'A'  missing=0，收缩：[1,10] 长 10、[2,10] 长 9 都不如 6；
          吐 s[3]='B' 时 need[B] 由 -1 加回 0，**不是正数**，
          所以 missing 不变、收缩继续——这正是负值富余量的用处；
          一路吐到 s[5]='C'，need[C] 变成 1，missing=1，left=6，退出
r=12 'C'  missing=0，收缩：[6,12] 长 7、[7,12] 长 6 都不更优，
          [8,12] 长 5 -> 记下，[9,12] "BANC" 长 4 -> 记下；
          再吐 s[9]='B' 就缺 B，missing=1，left=10，退出

最终 best_l=9、best_len=4，切片 s[9:13] = "BANC"，与样例一致。 若第 4 条坑写错（把记录挪到收缩循环之后），r=12 这一轮记下的会是 已经不再覆盖的 [10,12] "ANC"。

参考实现

solutions/leetcode/LC76/sol.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from typing import List, Optional


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        m = len(s)
        # need[c] = 还差多少个字符 c。允许为负，负值表示窗口里多带的富余量，
        # 这正是「t 含重复字符」能被正确处理的原因
        need = {}
        for ch in t:
            need[ch] = need.get(ch, 0) + 1
        # missing = 还差多少个字符（按出现次数计）。它把「逐个检查每种字符够不够」
        # 压成一个标量：missing == 0 当且仅当窗口已覆盖 t
        missing = len(t)
        left = 0                    # 窗口左端，闭区间；循环不变量：left 只增不减
        best_len = m + 1            # 哨兵：比任何真实窗口都长，用来区分「无解」
        best_l = 0
        for right, ch in enumerate(s):
            # 右端吞进一个字符。只有 need[ch] 仍为正，这个字符才真的补上了缺口；
            # 否则它只是富余，need[ch] 被减成负数，missing 不动
            if ch in need:
                if need[ch] > 0:
                    missing -= 1
                need[ch] -= 1
            # 覆盖成立后尽量压缩左端。左指针在整个外层循环中只前进不后退——
            # 右端右移只会让约束更松，已经越过的左端位置永远不可能重新变成最优
            while missing == 0:
                # 记录必须在吐字符**之前**：此刻的窗口才是合法的
                if right - left + 1 < best_len:
                    best_len = right - left + 1     # 闭区间长度，+1 不能少
                    best_l = left
                out = s[left]
                if out in need:
                    need[out] += 1
                    # 先加回再判断：只有从 0 变成 1 才是真的缺了一个，
                    # 吐掉富余字符（加回后仍 <= 0）不该让 missing 增加
                    if need[out] > 0:
                        missing += 1
                left += 1           # 左端单调右移，这一步之后窗口可能不再覆盖
        # 哨兵没被改写说明从未覆盖成功，按题面返回空串；
        # 切片右端是开区间，所以是 best_l + best_len
        return "" if best_len > m else s[best_l:best_l + best_len]
[:octicons-arrow-left-16: LC75](LC75.md)　[LC78 :octicons-arrow-right-16:](LC78.md)