最小覆盖子串

这道题真正在问什么

给两个字符串 s 和 t，在 s 中找出最短的连续子串，使它包含 t 的全部字符——注意是「包含」而非「等于」，窗口里允许夹杂无关字符；且 t 里的重复字符要按次数算，t = "AAB" 就必须凑够两个 A。比如 s = "ADOBECODEBANC"、t = "ABC"，答案是 "BANC"。找不到时返回空串。

为什么暴力枚举子串行不通

最直觉的做法是枚举所有子串、逐个检查是否覆盖 t：起点终点组合有 O(n²) 个，每次检查还要 O(n) 扫一遍统计字符，加起来 O(n³)，s 稍长就完全跑不动。

破局的观察有两条。第一，覆盖性有单调性：一个窗口若已覆盖 t，再往右扩只会多不会少，检查更长的窗口毫无意义——该做的是收缩，看它还能多短。第二，窗口每次只在两端进出一个字符，覆盖状态完全可以增量维护，不必每次从头重数。这两条合起来，就把问题逼向了「双指针一趟扫完」的滑动窗口（也叫双指针窗口）。

怎么高效判断窗口已覆盖 t

先用计数表 need 记下 t 中每个字符需要的个数，再用 win 记录当前窗口内各字符的实际个数。判断覆盖不必逐项对比整张表：额外维护一个变量 formed，表示「已经凑够次数的字符种数」，当 formed 等于 t 中不同字符的总种数 required 时，窗口即完成覆盖。

formed 的维护是增量的：右端吃进字符 c 后，若 win[c] 恰好追平 need[c]，formed 加一；左端挤出字符后，若该字符的计数跌破需求，formed 减一。每次进出只花 O(1)，这正是整个算法能保持线性的关键一环。

为什么覆盖后必须立刻收缩左边界

算法的节奏是「右扩补齐、左缩压短」交替：右指针一路吃字符，直到 formed == required；随即进入收缩循环，每一步先用当前窗口长度 r - l + 1 更新最优答案，再把 s[l] 挤出窗口、l 右移，直到覆盖被破坏，然后回到右扩。

这样做不漏最优解的理由是：对每一个可能的右端点 r，收缩过程恰好找到了以 r 结尾的最短覆盖窗口——继续缩就不覆盖了，说明已经缩到底。所有右端点各自的最短窗口都被比较过，全局最短自然在其中。另外「先记录再移动 l」的顺序不能反，先移再记会把当前这个合法窗口漏掉。

复杂度怎么算，哪些细节容易错

时间 O(n)：右指针扫一遍 s，左指针也只向右、累计最多走 n 步，每步的计数增减都是 O(1)；空间 O(k)，两张计数表最多存 t 中不同字符数个键。

两个高频翻车点：一是只比字符种类、不比出现次数——t 里的重复字符必须按 need[c] 的计数凑够，只用集合判断会把 "AAB" 当成只要一个 A；二是拿到第一个覆盖窗口就直接返回——第一个只是「最早」不是「最短」，必须让窗口继续滑到 s 末尾，把每个右端点的收缩结果都比完才能收工。