题目描述
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example1:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
NOTE
- If there is no such window in S that covers all characters in T, return the empty string “”.
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
解题思路
- 不会做，嘤嘤嘤，参考
- 致谢博主！
- 题目例子中的S有点长，换个短的 S = “ADBANC”，T = “ABC”，那么肉眼遍历一遍S呗，首先第一个是A，嗯很好，T中有，第二个是D，T中没有，不理它，第三个是B，嗯很好，T中有，第四个又是A，多了一个，礼多人不怪嘛，收下啦，第五个是N，一边凉快去，第六个终于是C了，那么貌似好像需要整个S串，其实不然，注意之前有多一个A，就算去掉第一个A，也没事，因为第四个A可以代替之，第二个D也可以去掉，因为不在T串中，第三个B就不能再去掉了，不然就没有B了。所以最终的答案就”BANC”了。
-
通过上面的描述，你有没有发现一个有趣的现象，先扩展，再收缩，就好像一个窗口一样，先扩大右边界，然后再收缩左边界，上面的例子中右边界无法扩大了后才开始收缩左边界，实际上对于复杂的例子，有可能是扩大右边界，然后缩小一下左边界，然后再扩大右边界等等。这就很像一个不停滑动的窗口了，这就是大名鼎鼎的滑动窗口 Sliding Window 了，简直是神器啊，能解很多子串，子数组，子序列等等的问题，是必须要熟练掌握的啊！
- 下面来考虑用代码来实现，先来回答一下前面埋下的伏笔，为啥要用 HashMap，而不是 HashSet，现在应该很显而易见了吧，因为要统计T串中字母的个数，而不是仅仅看某个字母是否在T串中出现。
- 统计好T串中字母的个数了之后，开始遍历S串，对于S中的每个遍历到的字母，都在 HashMap 中的映射值减1，如果减1后的映射值仍大于等于0，说明当前遍历到的字母是T串中的字母，使用一个计数器 cnt，使其自增1。
- 当 cnt 和T串字母个数相等时，说明此时的窗口已经包含了T串中的所有字母，此时更新一个 minLen 和结果 res，这里的 minLen 是一个全局变量，用来记录出现过的包含T串所有字母的最短的子串的长度，结果 res 就是这个最短的子串。
- 然后开始收缩左边界，由于遍历的时候，对映射值减了1，所以此时去除字母的时候，就要把减去的1加回来，此时如果加1后的值大于0了，说明此时少了一个T中的字母，那么 cnt 值就要减1了，然后移动左边界 left。
具体的步骤： - 先扫描一遍T，把对应的字符及其出现的次数存到 HashMap 中。 - 然后开始遍历S，就把遍历到的字母对应的 HashMap 中的 value 减一，如果减1后仍大于等于0，cnt 自增1。 - 如果 cnt 等于T串长度时，开始循环，纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移，如果某个移除掉的字母是T串中不可缺少的字母，那么 cnt 自减1，表示此时T串并没有完全匹配。
class Solution {
public:
string minWindow(string s, string t) {
string res;
int cnt = 0;
int minLen = INT_MAX;
int left = 0;
unordered_map<char, int> mmap;
for(auto c : t){
mmap[c]++;
}
for(int i = 0; i < s.size(); i++){
if(--mmap[s[i]] >= 0){
cnt++;
}
while(cnt == t.size()){
if(minLen > i - left + 1){
minLen = i - left + 1;
res = s.substr(left, minLen);
}
if(++mmap[s[left]] > 0){
--cnt;
}
++left;
}
}
return res;
}
};
