leetcode面试经典150题——33 最小覆盖子串（滑动窗口）

题目： 最小覆盖子串

描述：
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

leetcode链接

方法一：滑动窗口
题目解读：该题与32题（详细见上一篇讲解32串联所有单词的子串）很相似，唯一不同的是本题所求子串中不仅包含t中的所有字符，还可以包含其他的字符，因此所求子串和t是一个包含的关系，而32题所求子串和t的字符是一一对应的，没有多余的字符，即子串的长度等于t的长度，而此题子串的长度大于等于t的长度。
求解：同样的我们利用32题的滑动窗口的方法，过程完全一致，唯一不同该题的窗口为动态长度的，即定义一个窗口，初始长度为0，然后判断当前窗口是否包含t中所有的字符，如果包含，那么记录该窗口的长度并且维护一个最小的满足条件的窗口长度，并且left指针右移，即缩小窗口的长度。如果不包含t中所有字符，那么right指针右移，即增大窗口，循序以上操作。
那么我们如何判断窗口是否包含t中的所有字符呢，我们考虑最佳时间复杂度的做法，即为定义2个unordered_map,分别为map1和map2,map1记录中字母的出现次数，map2记录窗口字母的出现次数，然后判断map1和map2，如果map1中所有的关键字的值都小于等于map2，那么可以认为窗口包含了t中所有字符。这里在存储map2的时候，只需要存储在map1中出现过的关键字，含义即为只存储t中出现过的字符到map中，这样做节省了空间的消耗。
时间复杂度：o(Cn,+m) 时间包括指针的移动（窗口的枚举），为o(n)，和判断窗口是否包含t中字符的时间，即为哈希表的查询，设哈希表的大小为C,那么时间复杂度为o(Cn)，还有初始把t中所有字符插入哈希表的时间，为o(m)，所以总时间复杂度为o(Cn+m)。

过程如图所示，阴影部分为当前窗口，其中红色字体的字母为存储在哈希表中的元素，窗口内其它元素不进行存储

发现此时窗口不包含t中的所有元素，那么right指针右移，此时窗口包含t中所有的元素，记录此时的子串长度

然后left指针右移

class Solution {
public:
    unordered_map<char,int> smap,tmap;

    string minWindow(string s, string t) {
        int n = s.size(),m = t.size();
        int len = INT_MAX, ansL = -1, ansR = -1;
        for(auto &c : t){
            tmap[c]++;//存储t中单词出现的次数
        }
        int left = 0,right = -1;
        while(right<n){
        	//窗口右移
            if(tmap.find(s[++right])!=tmap.end()){//统计在t中出现过的字符的个数
                smap[s[right]]++;
            }
            while(check()&&left<=right){//如果窗口中包含s所有字符，那么left指针右边移
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    ansL = left;
                }
                if(tmap.find(s[left])!=tmap.end()){
                    smap[s[left]]--;
                }
                left++;
            }
        }
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
    bool check(){
        for(auto &p:tmap){
            if(smap[p.first]<p.second){
                return false;
            }
        }
        return true;
    }
};