算法题目：最小覆盖子串
给你一个字符串 s 和一个字符串 t 。请你找出在 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
-
对于
t中重复的字符，我们寻找的子字符串中该字符的数量必须不少于t中该字符的数量。 -
如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 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.length -
n == t.length -
1≤m,n≤105
-
s和t由英文字母组成
这道“最小覆盖子串”问题是算法中一个非常经典的题目，它考察的是对字符串处理和窗口思想的理解。直接使用暴力法（即检查s的每一个子串）效率会非常低，无法通过测试。解决这个问题的最优方法是滑动窗口（Sliding Window）。
解题思路：滑动窗口
滑动窗口可以理解为一个在字符串s上移动的“尺子”，这个“尺子”的左右两端就是我们所说的“窗口”。我们的目标是调整这个“尺子”的左右端点，使其框住的范围（即子串）恰好包含t中的所有字符，并找到这个“尺子”的最小长度。
具体步骤如下：
-
初始化需求列表：首先，我们需要知道我们需要哪些字符以及各需要多少个。我们可以用一个哈希表（在 JavaScript 中就是普通对象
Object）来记录字符串t中每个字符出现的次数。我们称之为needs。 -
定义窗口和指针：
-
我们用
left和right两个指针来表示窗口的左右边界，初始时都指向字符串s的开头（索引0）。 -
我们还需要另一个哈希表
window来记录当前窗口内包含了needs中字符的个数。 -
一个计数器
validCount用来记录window中有多少个字符已经满足了needs的要求（即数量上达到了要求）。例如，如果t是 "AAB"，那么当窗口中 'A' 的数量达到 2 时，'A' 这个字符就算满足要求了，validCount可以加 1。
-
-
移动窗口：
-
扩大窗口：我们不断地向右移动
right指针，将新的字符加入窗口。-
每加入一个字符
c，就更新window中c的计数。 -
如果
c是我们需要的字符（即c在needs中），并且它在window中的数量正好等于在needs中的数量，说明这个字符的要求已经满足，我们将validCount加 1。
-
-
缩小窗口：当
validCount的值等于needs中不同字符的总数时（例如，t="AABC"，needs里有A,B,C三种字符，那么就是3），说明当前窗口已经是一个可行解（即它已经覆盖了t）。-
此时，我们记录下这个窗口的长度，并和已知的最小长度比较，如果更小就更新最小长度和起始位置。
-
然后，我们尝试从左边缩小窗口，即向右移动
left指针。 -
移出一个字符
d，并更新window中d的计数。 -
如果
d是我们需要的字符，并且在移出之前它在window中的数量正好等于在needs中的数量，那么移出后，这个字符的要求就不再满足了，所以validCount要减 1。 -
我们持续缩小窗口，直到
validCount不再满足条件，然后回到扩大窗口的步骤。
-
-
-
循环与结束：
-
我们重复第 3 步，直到
right指针到达字符串s的末尾。 -
循环结束后，如果最小长度仍然是初始的极大值，说明没有找到任何符合条件的子串，返回
""。否则，根据记录的最小长度和起始位置，截取并返回结果。
-
JavaScript 实现
JavaScript
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
// 如果 t 的长度大于 s，不可能找到符合条件的子串
if (t.length > s.length) {
return "";
}
// needs 哈希表记录 t 中每个字符的需求数量
const needs = {};
for (const char of t) {
needs[char] = (needs[char] || 0) + 1;
}
// window 哈希表记录当前窗口中包含 t 中字符的数量
const window = {};
// left, right 指针分别指向窗口的左右边界
let left = 0, right = 0;
// validCount 记录窗口中满足 needs 条件的字符种类数
let validCount = 0;
// needsSize 记录 t 中不重复字符的种类数
const needsSize = Object.keys(needs).length;
// minLen 记录最小子串的长度，初始化为一个不可能达到的最大值
let minLen = Infinity;
// start 记录最小子串的起始索引
let start = 0;
// 开始滑动窗口
while (right < s.length) {
// c 是即将移入窗口的字符
const c = s[right];
// 右移窗口
right++;
// 如果 c 是 t 中需要的字符，则更新 window 计数
if (needs[c]) {
window[c] = (window[c] || 0) + 1;
// 如果某个字符在窗口中的数量达到了 t 中的需求数量
if (window[c] === needs[c]) {
// 满足条件的字符种类数 +1
validCount++;
}
}
// 当窗口中所有需要的字符数量都满足了 t 的要求时
// validCount === needsSize 表示找到了一个覆盖子串
while (validCount === needsSize) {
// 当前窗口的长度
const currentLen = right - left;
// 如果当前窗口长度小于已记录的最小长度，则更新
if (currentLen < minLen) {
minLen = currentLen;
start = left; // 记录这个最小子串的起始位置
}
// d 是即将移出窗口的字符
const d = s[left];
// 左移窗口
left++;
// 如果移出的字符 d 是 t 中需要的字符
if (needs[d]) {
// 如果 d 在窗口中的数量原本是正好满足需求的
if (window[d] === needs[d]) {
// 那么移出后就不再满足了，validCount -1
validCount--;
}
// 更新 window 计数
window[d]--;
}
}
}
// 如果 minLen 还是初始值，说明没有找到符合条件的子串
// 否则，根据记录的 start 和 minLen 截取子串并返回
return minLen === Infinity ? "" : s.substring(start, start + minLen);
};
复杂度分析
-
时间复杂度: O(m+n)，其中
m是字符串s的长度，n是字符串t的长度。-
我们首先遍历
t一次来构建needs哈希表，时间为 O(n)。 -
然后
left和right指针都各自最多遍历s一次。虽然有嵌套的while循环，但left指针的移动次数不会超过right，总体来看每个元素最多被访问两次（一次被right指针访问，一次被left指针访问）。所以滑动窗口部分的时间复杂度是 O(m)。 -
总时间复杂度为 O(m+n)。
-
-
空间复杂度: O(k)，其中
k是字符串t中不同字符的数量（或者说是字符集的大小）。- 我们需要
needs和window两个哈希表来存储字符计数，它们的大小最多为k。
- 我们需要