给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
> 思路
滑动窗口
> 代码
class Solution {
public:
string minWindow(string s, string t) {
int len1 = s.size();
int len2 = t.size();
if(len1 < len2) return "";
unordered_map<char,int> mp_s;
unordered_map<char,int> mp_t;
for(const auto& c:t){
mp_t[c]++;
}
int l = 0;
int r = 0;
int valid = 0;
int start = 0;
int len_r = INT_MAX;
while(r < len1){
// c是要移入窗口的字符
char c = s[r];
// 右移指针
r++;
// 进行窗口更新
if(mp_t.count(c)){
mp_s[c]++;
if(mp_s[c] == mp_t[c]){
valid++;
}
}
//判断左侧窗口需要收缩
while(valid == mp_t.size()){
// 在这里更新最小覆盖子串
if(r - l < len_r){
start = l;
len_r = r - l;
}
// d是将移出窗口的字符
char d = s[l];
//窗口左移
l++;
// 进行窗口更新
if(mp_t.count(d)){
if(mp_t[d] == mp_s[d]){
valid--;
}
mp_s[d]--;
}
}
}
return len_r == INT_MAX?"":s.substr(start,len_r);
}
};