最小覆盖子串
Minimum Window Substring
在字符串 s 中找最短的子串，使它包含 t 中的所有字符（包括重复次数）。
在力扣中练习题目描述
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在
O(m + n) 时间内解决此问题的算法吗？解题思路
主解法
滑动窗口 · 覆盖计数
右指针扩到覆盖，左指针缩到最短
暴力枚举所有子串再检查是否覆盖 t，是 O(n²) 甚至更高。
用滑动窗口：右指针不断右移，把字符加入窗口；当窗口已经覆盖 t 的全部字符时，左指针开始右移，尽量缩短窗口。每次缩短前用当前长度更新答案。
关键是维护 formed：它统计“已经满足次数要求的字符种类数”。只有某个字符的窗口次数刚好等于 need 时，formed 才加一；缩小时次数跌破 need，formed 才减一。这样重复字符（例如 t 里有两个 a）不会被误判。
自拟主例 s = "abacbd"、t = "abc"：窗口扩到 abac 时首次覆盖，缩短到 bac 后 b 被移出，formed 下降，窗口重新开始扩展。
分步图解
t = "abc" 需要 3 种字符；窗口为空，best 还没出现。
- required
- 3
分步图解
窗口 [0, 3] 覆盖了 t；长度 4，更新 best = "abac"。
- 长度
- 4
每个字符最多被左右指针各访问一次，时间 O(n)，空间 O(128)。
时间 O(n)空间 O(128)
易错点
- formed 在每次遇到目标字符时都加一：重复字符会让它虚高，窗口其实还没覆盖。
- 收缩时先 left++ 再减计数：移出的字符和窗口状态对不上。
- 只在扩展时更新答案：最短窗口往往是在收缩过程中出现的。
- t 比 s 长或 t 为空：需要单独处理边界。
代码与演示
演示输入
s = "abacbd", t = "abc"t = "abc" 需要 3 种字符；窗口为空，best 还没出现。
- required
- 3
查看 C++ 代码
延伸阅读
- “覆盖所有字符”用 formed 统计种类，比每次比较两个 128 长度数组更直观，也更适合字符集不固定的情况。
- 同类题：最小覆盖子串的变体包括“包含所有元音”“最多 k 个不同字符”等，窗口条件不同，扩展/收缩骨架相同。