子串

 

 

class Solution {
public:
    string minWindow(string s, string t) {
        if (s == t)
            return s; // 如果这2个串一样最小覆盖就是s
        int len_s = s.size();
        int len_t = t.size();
        int bestlen = INT_MAX; // int的最大值,用于存最小覆盖子串的长度
        int beststart = -1; // 满足条件的最小覆盖子串的起点在s串
        int l=0;
        int r=0;
        int cnt[52];

        for(int i=0;i<52;i++){
            cnt[i]=0;
        }
        for(int i=0;i<len_t;i++){
        if(t[i]>='a'&&t[i]<='z')    cnt[t[i]-'a']= cnt[t[i]-'a']+1;
        else if(t[i]>='A'&&t[i]<='Z'){
            cnt[t[i]-'A'+26]= cnt[t[i]-'A'+26]+1;
        }
        }
        while(r<len_s){
            if(((s[r]>='a'&&s[r]<='z')&&(--cnt[s[r]-'a']>=0))||((s[r]>='A'&&s[r]<='Z')&&(--cnt[s[r]-'A'+26]>=0))){//无论if条件是否满足都会先--
                len_t--;//如果是t中必要的字符而且还没用完
            }
            while(len_t==0){//
                //t中字符已经全覆盖，窗口已满
                if(bestlen>r-l+1){
                    bestlen=r-l+1;
                    beststart=l;
                }
                if(((s[l]>='a'&&s[l]<='z')&&(++cnt[s[l]-'a']>0))||((s[l]>='A'&&s[l]<='Z')&&(++cnt[s[l]-'A'+26]>0))){
                    //收缩l处影响t中必要字符，那所需字符会增加len_t++
                    len_t++;
                }
                l++;//收缩窗口
            }
            r++;
        }
        if (beststart == -1){
             return "";
        }
        else{
            return s.substr(beststart,bestlen);
        }
    }
};