最小覆盖子串
给定两个字符串 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 <= 10^5s和t由英文字母组成
进阶： 你能设计一个在 O(m + n) 时间内解决此问题的算法吗？
滑动窗口-哈希计数：
class Solution {
public:
string minWindow(string s, string t) {
if (s.size() < t.size())
{
return "";
}
vector<int> need(128, 0);
vector<int> window(128, 0);
int required = 0;
for (char c : t)
{
if (need[c] == 0)
{
required++;
}
need[c]++;
}
int formed = 0;
int left = 0;
int start = 0;
int minLen = INT_MAX;
for (int right = 0; right < s.size(); right++)
{
char c = s[right];
window[c]++;
if (need[c] > 0 && window[c] == need[c])
{
formed++;
}
while (formed == required)
{
if (right - left + 1 < minLen)
{
minLen = right - left + 1;
start = left;
}
char d = s[left];
if (need[d] > 0 && window[d] == need[d])
{
formed--;
}
window[d]--;
left++;
}
}
if (minLen == INT_MAX)
{
return "";
}
return s.substr(start, minLen);
}
};
核心思想
这题要求的是 s 中最短的一段连续子串，并且这段子串要覆盖 t 中的所有字符。
注意，这里说的是“包含每一个字符”，而且包括重复字符。
例如：
t = "AABC"
那么合法窗口中必须至少有：
2个'A'1个'B'1个'C'
只包含一个 'A' 是不够的。
所以我们不能只判断字符是否出现，而要判断每个字符出现的次数是否达到要求。
核心思路是滑动窗口：
- 右边界
right不断向右移动，扩大窗口，直到窗口覆盖t。 - 当窗口已经合法时，左边界
left尽量向右移动，缩小窗口，寻找当前右边界下的最短合法窗口。 - 每次窗口合法时，都用当前窗口长度更新答案。
状态含义
代码中有两个计数数组：
vector<int> need(128, 0);
vector<int> window(128, 0);
其中：
need[c]：字符c在t中需要出现的次数window[c]：字符c在当前窗口[left, right]中出现的次数
再看两个变量：
int required;
int formed;
required：t中一共有多少种不同字符需要满足formed：当前窗口中已经有多少种字符满足了需要的次数
当：
formed == required
说明 t 中每一种字符都已经在窗口里出现了足够次数。
也就是说，当前窗口是一个合法窗口。
合法窗口的判断条件
窗口 [left, right] 合法，当且仅当对于 t 中出现过的每个字符 c，都有：
window[c] >= need[c]
也就是说，窗口中每种字符的数量都不少于 t 中要求的数量。
如果每次都遍历所有字符检查这个条件，也可以通过，因为英文字母种类有限。
但代码使用了更高效、更清晰的 formed 来记录有多少种字符已经达标。
当加入一个字符 c 后：
window[c]++;
如果此时刚好满足：
need[c] > 0 && window[c] == need[c]
说明字符 c 从“不达标”变成了“达标”，所以：
formed++;
当移除左端字符 d 前，如果满足：
need[d] > 0 && window[d] == need[d]
说明这个字符现在刚好达标。
如果把它移除，窗口里这个字符就会变成不达标，所以要先：
formed--;
再执行：
window[d]--;
为什么先扩张再收缩
右边界 right 扩张的目的，是让窗口从不合法变成合法。
当 formed < required 时，说明窗口还缺少某些字符，或者某些字符数量不够。
这时缩小窗口没有意义，因为缩小只会让字符更少，更不可能变合法。
所以必须继续移动 right。
当 formed == required 时，说明当前窗口已经覆盖了 t。
但它不一定是最短的，因为左边可能包含一些多余字符。
所以此时不断移动 left，尝试删除窗口左侧字符。
只要删除后窗口仍然合法，就说明原来的窗口还可以更短。
直到某一次删除会导致窗口不合法，当前这一轮收缩才停止。
这样对于每一个右边界，算法都能找到以它为右端点的最短合法窗口。
公式推导
当前窗口范围是：
[left, right]
窗口长度是：
right - left + 1
当 formed == required 时，窗口合法，可以用当前长度更新答案：
if (right - left + 1 < minLen)
{
minLen = right - left + 1;
start = left;
}
然后继续移动 left，尝试得到更短的合法窗口。
如果移除 s[left] 后窗口仍然合法，那么新的窗口长度更短，继续更新。
如果移除 s[left] 后窗口不合法，说明当前右边界下已经不能再缩短了，需要继续移动 right 寻找新的合法窗口。
为什么重复字符也能正确处理
这题最容易出错的地方就是重复字符。
例如：
s = "AAAB"
t = "AAB"
t 里面需要两个 'A'。
如果窗口里只有一个 'A'，不能算覆盖。
代码通过 need[c] 和 window[c] 的具体次数来判断是否达标：
window[c] == need[c]
只有当窗口里的数量达到 t 的要求时，formed 才会增加。
如果窗口里某个字符数量超过要求，例如需要 2 个 'A'，窗口里有 3 个 'A'，那么它仍然只算一种字符达标，不会重复增加 formed。
这保证了重复字符会被正确处理。
正确性证明
我们证明：算法返回的字符串是 s 中覆盖 t 的最短子串。
结论 1：算法记录的每个候选答案都是合法窗口
算法只会在：
while (formed == required)
内部更新答案。
而 formed == required 表示 t 中每一种字符在当前窗口中都已经达到需要的次数。
也就是对于所有 t 中出现过的字符 c，都有：
window[c] >= need[c]
所以当前窗口一定覆盖了 t。
因此算法记录的每个候选答案都是合法窗口。
结论 2：对于每个右端点，算法都会找到最短合法窗口
固定某个右端点 right。
当窗口 [left, right] 第一次满足 formed == required 时，它是一个合法窗口。
接下来算法会不断右移 left。
每移动一次，如果窗口仍然合法，就继续更新答案并继续收缩。
直到移除某个左端字符后，窗口不再合法，收缩停止。
因此，在这个固定的 right 下，算法已经尝试了所有可以继续缩短的合法窗口。
最后一次被记录的合法窗口，就是以当前 right 为右端点的最短合法窗口。
结论 3：全局最短窗口一定会被枚举到
设全局最短覆盖子串是：
s[L ... R]
当算法的右端点移动到 R 时，左端点一定会在收缩过程中尽量右移。
因为 s[L ... R] 是合法窗口，所以算法在 right = R 时一定会进入收缩过程。
又因为 s[L ... R] 是以 R 为右端点的最短合法窗口之一，算法收缩到这个位置时会记录它。
题目保证答案唯一，所以最终记录的最短窗口就是这个答案。
得出结论
由结论 1 可知，算法不会记录非法窗口。
由结论 2 可知，对于每个右端点，算法不会漏掉该右端点下的最短合法窗口。
由结论 3 可知，全局最短合法窗口一定会被算法记录。
所以算法返回的结果正确。
举例理解
以：
s = "ADOBECODEBANC", t = "ABC"
为例。
t 中需要：
'A'：1次'B'：1次'C'：1次
开始时不断移动 right。
当窗口第一次变成：
"ADOBEC"
它已经包含 A、B、C，所以合法，先记录长度 6。
然后尝试移动 left。
如果去掉左边的 'A'，窗口就不再包含 A，所以收缩停止。
接着继续右移 right，直到后面再次形成合法窗口。
当扫描到：
"BANC"
时，它包含 A、B、C，长度为 4，比之前更短，所以更新答案。
最终返回 "BANC"。
复杂度分析
设 m = s.length，n = t.length。
初始化 need 数组需要遍历 t，时间复杂度是：
O(n)
滑动窗口中：
right从左到右最多移动m次left从左到右最多移动m次
所以窗口整体扫描时间复杂度是：
O(m)
因此总时间复杂度是：
O(m + n)
额外使用两个长度为 128 的计数数组，所以空间复杂度是：
O(1)