BM90　最小覆盖子串¶

较难通过率 27.35%python3核心代码模式样例通过牛客 AC字符串哈希双指针

一句话

滑动窗口：右指针扩到「够了」就收左指针，两个指针各走一遍。

解题思路¶

这题考什么¶

两条单调性凑出线性解法。其一：若 S[l..r] 已经覆盖 T，把 r 继续右移只会更长、不会更优；其二：右端点固定时，可行的左端点构成一段前缀（l 越小越容易覆盖），所以每个右端点只需要关心最靠右的那个可行左端点。两条合起来意味着左端点随右端点单调不减，这正是滑动窗口成立的前提，也是它 O(n) 的来源。见双指针与滑动窗口。

一张计数表加一个标量：

need[c]   T 里字符 c 还缺几个，允许为负（负值表示窗口里多出来的份数）
missing   还差多少个字符才能覆盖 T，重复字符按重数计

右指针吃进字符 c 时 need[c] -= 1；只有在减之前 need[c] > 0 （说明这一个确实在补缺，而不是多余的第二份）才让 missing -= 1。 T 里有重复字符时（样例 "AA"），这条规则保证两个 "A" 都要凑齐。

missing == 0 说明窗口已覆盖 T，此时把左端收到不能再收：左端字符若是「窗口里恰好只剩必需的那一份」就停手，否则吐掉并右移。收完结算一次答案，再主动吐掉一个必需字符让窗口失效，去找下一个可行窗口。

走一遍 S = "abcAbA"、T = "AA"（need = {"A": 2}，missing = 2）：

r  字符  窗口        need["A"]  missing  动作
0   a    [a]              2        2     与 T 无关
1   b    [ab]             2        2
2   c    [abc]            2        2
3   A    [abcA]           1        1     补到一个
4   b    [abcAb]          1        1
5   A    [abcAbA]         0        0     覆盖成立，开始收左指针
         a、b、c 都与 T 无关，逐个吐掉
         收到 [AbA] 时再收就要吐掉 "A"，停手
         答案 = "AbA"，长度 3

数据规模与复杂度¶

|S|, |T| <= 1e4，仅含大小写英文字母，时限「其他语言 2 秒」。每个字符至多进窗一次、出窗一次，时间 O(n + m)，空间 O(字符集) = O(52)——need 表最多装下 T 里出现过的字符种类。暴力枚举左右端点再逐个数字符是 O(n^2 * m) = 1e4 * 1e4 * 1e4 = 1e12 量级，完全不可行。

坑在哪¶

左指针只能单调右移，绝不能因为换了右端点就退回去重扫。一旦允许回退，总移动次数就从 O(n) 退化回 O(n^2)；而上面那条单调性保证了不会漏解——被左指针甩掉的左端点，配任何更靠右的右端点都只会得到更长的窗口。
结算完答案必须主动把 S[l] 吐回去、missing += 1、l += 1，人为破坏覆盖。不这么做，missing 会一直是 0，外层的提前 continue 拦不住任何字符，内层的收缩循环则在同一个位置反复空转。
收缩的停止条件是「该字符属于 T 且 need 已经归零」。 need[lc] == 0 意味着窗口里这个字符恰好只剩必需的那一份，再吐一个覆盖就破了；need[lc] < 0 说明还有富余，可以放心吐掉并加回一份。
只记 (best_l, best_len)，最后再切一次片。每次窗口成立都拷一份子串出来，常数会被抬到无法接受的程度。
best_len 初值取 n + 1：任何合法窗口长度都不超过 n，所以末尾用 best_len > n 就能判出「一次都没成立过」，返回空串。初值取 0 或 n 都会与合法答案混淆。
题面保证满足条件的最短子串唯一，所以更新答案时用严格 < 或 <= 都不影响结果。

参考实现¶

solutions/nowcoder/BM90/sol.py
from typing import List, Optional


class Solution:
    def minWindow(self, S: str, T: str) -> str:
        n, m = len(S), len(T)
        # T 为空或比 S 还长时不可能有解，省掉整趟扫描
        if m == 0 or n < m:
            return ""

        # need[c] 记 c 还缺几个；扫描中会变成负数，负值即窗口里多出来的份数
        need = {}
        for c in T:
            need[c] = need.get(c, 0) + 1
        missing = m                     # 还差几个字符（重复字符按重数计）

        # best_len 取 n+1 这个不可能的长度当哨兵，末尾据此判断有没有解
        best_len, best_l = n + 1, 0
        l = 0
        for r, c in enumerate(S):
            if c in need:
                if need[c] > 0:         # 这一个是在补缺，不是多余的第二份
                    missing -= 1
                need[c] -= 1
            # 还没覆盖 T，继续扩右边界
            if missing:
                continue
            # 窗口已覆盖 T：把左边界收到不能再收，得到该右端点下的最短窗口
            while True:
                lc = S[l]
                if lc in need and need[lc] == 0:
                    break               # 这一份是必需的，再吐覆盖就破了
                if lc in need:
                    need[lc] += 1       # 吐掉的是多余的那份，覆盖仍成立
                l += 1                  # 左界只前进不后退，全程累计移动 O(n) 次
            if r - l + 1 < best_len:
                best_len, best_l = r - l + 1, l   # 只记起点与长度，避免反复切片
            # 主动吐掉一个必需字符，让窗口失效，右指针才能继续去找下一个可行窗口
            need[S[l]] += 1
            missing += 1
            l += 1
        # 哨兵没被刷新过说明无解；否则按记录的起点与长度切出答案
        return "" if best_len > n else S[best_l:best_l + best_len]

BM90 最小覆盖子串¶