LeetCode 76. 最小覆盖子串

思路

暴力就是枚举终点 i，找出里 i 最近的起点 j，再去更新答案，可以发现起点随终点单调往后，因此可以滑动窗口优化

如何快速判断当前窗口是否包含子串所有字符

• 哈希表 word 存储子串所有字符出现的次数，window 存储当前窗口所有字符出现的次数
• 变量 cnt 记录当前窗口里，有效字符的个数
• 当 cnt 等于所有字符的出现次数时，表明已经包含子串, 尝试更新答案

维护变量 cnt

假设新增的字符为 c

• 如果 window[c]<word[c]，cnt++；否则 cnt 不变，因为该字符已经冗余

代码

class Solution {
public:
    unordered_map<char,int> hashatble,window;
    string minWindow(string s, string t) {
        for(auto i:t)   hashatble[i]++;
        string res;
        for(int i=0,j=0,cnt=0;i<s.size();i++)
        {
            //维护窗口
            window[s[i]]++;//右边界右移
            if(window[s[i]]<=hashatble[s[i]]) cnt++;//更新cnt
            while(window[s[j]]>hashatble[s[j]])//如果左边界是冗余的
            {
                window[s[j]]--;
                j++;
            }
            //如果当前窗口包含了子串，则更新答案
            if(cnt==t.size())
                if(!res.size()||i-j+1<res.size())
                res=s.substr(j,i-j+1);
        }
        return res;
    }
};