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…

leetcode_minimum_window_substring.cpp

class Solution {
public:
    string minWindow(string S, string T) {
        if (S.empty() || T.empty())
            return "";
        tr1::unordered_map<char, int>::iterator iter;
        tr1::unordered_map<char, int> MT;
        for (int i = 0; i < T.length(); ++i) {
            iter = MT.find(T[i]);
            if (iter == MT.end())
                MT[T[i]] = 1;
            else
                iter->second++;
        }
        tr1::unordered_map<char, int>::iterator iter1;
        tr1::unordered_map<char, int> MS;
        int beg = 0;
        int end = 0;
        int mini = -1;
        int left = -1;
        while (end <= S.length()) {
            bool flag = true;
            for (iter = MT.begin(); iter != MT.end(); ++iter) {
                iter1 = MS.find(iter->first);
                if (iter1 == MS.end() || iter1->second < iter->second) {
                    flag = false;
                    break;
                }
            }
            if (flag == true) {
                if (mini == -1 || end - beg < mini) {
                    mini = end - beg;
                    left = beg;
                }
                iter = MT.find(S[beg]);
                while (iter == MT.end()) {
                    beg++;
                    if (end - beg < mini) {
                        mini = end - beg;
                        left = beg;
                    }
                    iter = MT.find(S[beg]);
                }
                MS[S[beg++]]--;
            }
            else if (end == S.length()) {
                break;
            }
            else {
                while (end < S.length()) {
                    char c = S[end++];
                    iter = MT.find(c);
                    if (iter != MT.end()) {
                        if (MS.find(c) == MS.end())
                            MS[c] = 1;
                        else
                            MS[c]++;
                        break;
                    }
                }
            }
        }
        return mini == -1 ? "" : S.substr(left, mini);
    }
};