【LeetCode解答】Minimum Window Substring

设置两个指针。后指针往后扫S到包含T所有字符即停止，然后前指针往后收缩找到最小窗口。

class Solution {
public:
    string minWindow(string S, string T) {
        if(S.empty()||T.empty()||S.length()<T.length()) return "";
        vector<int> cnt1('z'-'A'+1,0);
        vector<int> cnt2('z'-'A'+1,0);
        int cnt=0;
        int pos=0;
        int minlen=S.length();
        int minpos=-1;
        for(int i=0;i<T.length();i++)
            cnt1[T[i]-'A']++;

        for(int i=0;i<S.length();i++)
        {
            if(cnt1[S[i]-'A'])
            {
                cnt2[S[i]-'A']++;
                if(cnt1[S[i]-'A']>=cnt2[S[i]-'A'])
                    cnt++;
            }
            if(T.length()==cnt)
            {
                while(pos<=i)
                {
                    if(cnt1[S[pos]-'A'])
                    {
                        if(cnt1[S[pos]-'A']<cnt2[S[pos]-'A']) cnt2[S[pos]-'A']--;
                        else break;
                    }
                    pos++;
                }
                if(i-pos+1<=minlen) minlen=i-pos+1,minpos=pos;
            }
        }
        return -1!=minpos?S.substr(minpos,minlen):"";
    }
};