题解 | #最小覆盖子串#

/*
	HW双指针3 最小覆盖子串

*/
class Solution {
public:
    unordered_map<char,int>hash;
    bool check()
    {
        for(auto it=hash.begin();it!=hash.end();it++){
            if(it->second<=0)return false;
        }
        return true;
    }

    string minWindow(string S, string T) {
        int lens=S.length(),lent=T.length();
        for(int i=0;i<lent;i++){
            if(hash.count(T[i]))hash[T[i]]--;
            else hash[T[i]]=0;
        }
        int lo=0,hi=0;
        int cnt=lens+1;
        int l=-1,r=-1;
        for(;hi<lens;hi++){
            char ch=S[hi];
            if(hash.count(ch))hash[ch]++;
            while(check()){
                if(cnt>hi-lo+1){
                    cnt=hi-lo+1;
                    l=lo;
                    r=hi;
                }
                char cl=S[lo];
                if(hash.count(cl)){
                    hash[cl]--;
                }
                lo++;
            }
        }
        if(l==-1)return "";
        return string(S.begin()+l,S.begin()+r+1);
    }
};