76 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 empty string "".
• If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution

class Solution {
public:
    string minWindow(string s, string t) {
        int ns = s.size(), nt = t.size();
        string res = "";
        if ( ns < nt ) return res;
        unordered_map<char, int> dict;
        queue<int> index;
        int count = 0, min_length = ns, istart = -1;
        for ( int i = 0; i <= nt-1; i++ ) {
            if ( dict.find(t[i]) == dict.end() ) {
                dict[t[i]] = 1;
                count += 1;
            }
            else dict[t[i]] += 1;
        }
        for ( int i = 0; i <= ns-1; i++ ) {
            if ( dict.find(s[i]) == dict.end() ) continue;
            index.push(i);
            dict[s[i]] -= 1;
            if ( dict[s[i]] >= 1 ) continue;
            if ( dict[s[i]] == 0 ) count -= 1;
            if ( dict[s[i]] <= -1 ) {
                while ( ! index.empty() ) {
                    int j = index.front();
                    if ( dict[s[j]] >= 0 ) break;
                    dict[s[j]] += 1;
                    index.pop();
                }
            }
            if ( count != 0 ) continue;
            if ( (i-index.front()+1) <= min_length ) {
                istart = index.front();
                min_length = i - index.front() + 1;
            }
        }
        if ( istart == -1 ) return res;
        return s.substr(istart, min_length);
    }
};

Notes
The flowchart of examine one character goes as follows: