Minimum Window Substring

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

class Solution {//beware of duplicates!
    struct Pair{int pos; char c;Pair(int a,char b):pos(a),c(b){}};
public:
//expand the end index of the window of S one char at a time
//at the same time, try to shrink the front index as much as possible
//while keep the window containing all T-char's
    string minWindow(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (S.length() < T.length()) return "";
        vector<int> isT(300, false);//used to quick check if is a T-char, and count dups!
        for(int ii = 0; ii < T.length(); ++ii){
            ++isT[T[ii]];
        }
        int wStart = 0;//window start pos
        while(!isT[S[wStart]] && wStart < S.length()){++wStart;}
        if (wStart == S.length()) return "";

        int house = 0;//0 T-char so far        
        int const fullHouse = T.length();//total 
        //indicate if all T-char's are in the window
        string result(S);
        vector<int> countT(300,0);//count occurance in the window
        deque<Pair> posChar;//the positions of the T-char in window
        
        for(int wEnd = wStart; wEnd < S.length(); ++wEnd){
            char const sChar = S[wEnd];
            if (isT[sChar]){
                posChar.push_back(Pair(wEnd, sChar));//register position and T-char
                if(countT[sChar] < isT[sChar]) ++house;//register new/dup T-char showing up
                ++countT[sChar];//register count of this T-char
                if (fullHouse == house && result.size() > (wEnd-wStart+1)) result = S.substr(wStart, wEnd-wStart+1);
                //full house and short window, potential result!
                if (countT[sChar] > isT[sChar]){
                //if sChar shows more than in T in the window
                //the window may be qualified for shrinking
                    while(!posChar.empty()){
                        wStart = posChar.front().pos;
                        char wChar = posChar.front().c;
                        if (fullHouse == house && result.size() > (wEnd-wStart+1)) result = S.substr(wStart, wEnd-wStart+1);
                        if (countT[wChar] > isT[wChar]){
                            --countT[wChar];//once full house, always full house
                            posChar.pop_front();
                            continue;
                        }else break;
                    }//while posChar not empty
                }//if count > 1
            }else{//redundent char, not in T-char, not optimal for result
                continue;
            }//if-else 
        }//for wEnd
        if (fullHouse != house) return "";
        return result;
    }
};