class Solution {
public:
    string minWindow(string S, string T) {
        if (T.length() > S.length()) return "";

        //    Build Dict: Yes chars in T could be duplicated        
        unordered_map<char, int> dict;
        for (int i = 0; i < T.length(); i++)
        {
            if (dict.find(T[i]) == dict.end())        dict.insert(make_pair(T[i], 1));
            else                                    dict[T[i]] ++;
        }

        //    Build Indices - char - cnt        
        size_t ttlCnt = 0;
        int iLeft = 0;
        int minL = 0, minLen = std::numeric_limits<int>::max();
        unordered_map<char, size_t> rec;
        for (int i = 0; i < S.length(); i++)
        {
            char c = S[i];
            if (dict.find(c) != dict.end())
            {
                if (rec.find(c) == rec.end())    rec[c] = 1;
                else                            rec[c] ++;

                if (rec[c] == dict[c]) ttlCnt++;
                if (ttlCnt == dict.size())
                {
                    //    Shrink from Left
                    while ( dict.find(S[iLeft]) == dict.end() ||    // irrelavant char?
                            (iLeft < i && rec[S[iLeft]] > dict[S[iLeft]])) // redundant char?
                    {
                        if (dict.find(S[iLeft]) != dict.end())
                            rec[S[iLeft]] --;
                        iLeft++;
                    }
                    //    Update record
                    if ((i - iLeft + 1) < minLen)
                    {
                        minL = iLeft;
                        minLen = (i - iLeft + 1);
                    }
                }
            }
        }
        if (minLen == std::numeric_limits<int>::max()) return "";
        return S.substr(minL, minLen);
    }
};