class Solution {
public:
    string minWindow(string S, string T) {
        string ans = "";
        if(S.size() < T.size() )
            return ans;
        
        unordered_map<char,int> count;
        unordered_set<char> charInT;
        unordered_map<char,int> countT;
        
        for(int i = 0; i < T.size(); i++)
        {
            charInT.insert(T[i]);
            countT[T[i]]++;
        }
        
        int ansI = 0, ansJ = 0;
        // 先找第一个合法的
        for(int i = 0; i < S.size(); i++)
        {
            if(charInT.find(S[i]) != charInT.end())
            {
                count[S[i]]++;
                // 如果都找到了
                if(count.size() == countT.size())
                {
                    bool flag = true;
                    for(unordered_map<char,int>::iterator itr = countT.begin(); itr != countT.end(); itr++)
                    {
                        if(itr->second > count[itr->first])
                            flag = false; // 还没都匹配
                    }
                    if(flag)
                    {
                        ansJ = i;
                        ans = S.substr(ansI,ansJ+1);
                        break;
                    }
                }
            }
        }
        // 往后遍历
        for(int m = 0; m < S.size(); m++)
        {
            if(charInT.find(S[m]) == charInT.end())
                ansI++; // 往前走1个是安全的
            else 
            {
                count[S[m]]--;
                if(count[S[m]] >= countT[S[m]])
                    ansI++;
                else
                {
                    if(ans.size() > ansJ - m + 1)
                        ans = S.substr(m,ansJ - m +1);
                    // find new end
                    int temp = ansJ;
                    temp++;
                    while(temp<S.size() && S[temp] != S[m])
                    {
                        if(charInT.find(S[temp]) != charInT.end())
                            count[S[temp]]++; // 记录新加进来了合法的
                        temp++;
                    }
                    if(temp == S.size()) // 到了最后也没找到
                    {
                        return ans;
                    }
                    else
                    {
                        ansJ = temp;
                        count[S[temp]]++;
                    }
                }
            }
        }
    }
};