描述
给你一个字符串 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 由英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
C++代码
class Solution {
public:
string minWindow(string s, string t) {
// need: 记录t中字符出现次数
// window: 记录窗口中相应字符的出现次数
unordered_map<char, int> need, window;
for(char c: t) need[c]++;
int left=0, right=0;
int cnt = 0; // 窗口中满足need条件的字符个数
int start = 0, minLen = INT_MAX;
while(right < s.size()){
// c是将移入窗口的字符
char c = s[right];
// 扩大窗口
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c])
cnt++;
}
// 判断左窗口是否要收缩
while(cnt == need.size()){
if(right-left < minLen){
minLen = right - left;
start = left;
}
// d是将移出窗口的字符
char d = s[left];
// 缩小窗口
left++;
if(need.count(d)){
if(window[d] == need[d]){
cnt--;
}
window[d]--;
}
}
}
// 返回最小覆盖子串
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}
};
