namespace MinimumWindowSubString {
    class Solution {
    public:
        string minWindow(string S, string T) { // Note: T could contain duplicated entries, such as "aab"
            if (T.empty()) return "";
    
            int alphaSet[256];
            fill_n(alphaSet, 256, 0);
            for (int i = 0; i < T.size(); i++) {
                alphaSet[T[i]]++;
            }
    
            int curAlphaSet[256];
            fill_n(curAlphaSet, 256, 0);
    
            int end = 0;
            int start = 0;
            int minStart = 0;
            int minLen = INT_MAX;
            int uniqueCount = 0;
            while (end < S.size()) {
                // move end forward
                char charEnd = S[end];
                if (alphaSet[charEnd] > 0) {
                    curAlphaSet[charEnd]++;
                    if (curAlphaSet[charEnd] <= alphaSet[charEnd]) uniqueCount++;
                    if (uniqueCount == T.size()) {
                        // move forward start
                        
                        while (start <= S.size() - T.size()) {
                            if (minLen > end - start + 1) {
                                minLen = end - start + 1;
                                minStart = start;
                            }
                            char charStart = S[start];
                            if (alphaSet[charStart] > 0) {
                                curAlphaSet[charStart]--;
                                if (curAlphaSet[charStart] < alphaSet[charStart]) {
                                    uniqueCount--;
                                    start++;
                                    break;
                                }
                            }
                            start++;
                        }
                    }
                }
                end++;
            }
    
            return minLen > S.size()? "": S.substr(minStart, minLen);
        }
    };
}