滑动窗口延申题：最小覆盖子串

class Solution {
private:
    bool coverall(unordered_map<char,int> smap,string t){
        for(int j=0;j<t.size();j++){
            auto found=smap.find(t[j]);
            if(found==smap.end()){
                return false;
            }
            else{
                --found->second;
                if(found->second==0)
                {
                    smap.erase(found);
                }
            }
        }
       return true; 
    }

public:
    string minWindow(string s, string t) {
        unordered_map<char,int> smap;
        int start=0;
        int minstart;
        int ans=INT_MAX;
        string subs;
        for(int end=0;end<s.size();end++){
            smap[s[end]]++;
            //cout<<"start:"<
            while(end-start+1>=t.size() && coverall(smap,t)){
                //cout<<"start:"<
                if(ans>end-start+1){
                    ans=end-start+1;
                    //cout<<"start:"<
                    subs=s.substr(start,end-start+1);
                }
                auto found=smap.find(s[start]);
                smap[s[start]]--;
                //cout<<"start:"<
                if(smap[s[start]]==0){
                    smap.erase(found);
                }
                start++;
            }
            }
        return subs;
        }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

由上一道接水果的题知道了用哈希表记录出现的种类和数量。
这道题的实质是要求s字串的种类和数量必须大于等于t的种类和数量
这道题自己写出来了，但是超时，下面是简化版：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> smap;
        unordered_map<char,int> tmap;
        for(int i=0;i<t.size();i++){
            tmap[t[i]]++;
        }
        int start=0;
        int cnt=0;
        string subs;
        for(int end=0;end<s.size();end++){
            smap[s[end]]++;
            if(smap[s[end]]<=tmap[s[end]]){
                cnt++;
            }
            while(smap[s[start]]>tmap[s[start]]){
                smap[s[start++]]--;
            }
            if(cnt==t.size()){
                if(subs.empty() || end-start+1 < subs.size()){
                    subs=s.substr(start,end-start+1);
                }
            }
            //cout<<"start:"<
            }
        return subs;
        }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29