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).

Example:

Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”

We use maps to maintain the frequency of the characters in T and S.
We also use two pointers to maintain a sliding window. Once the sliding window contains enough chars, we move the left ptrs forward and srhink the windows the the smallest possible.

class Solution {
public:
    string minWindow(string s, string t) {
        string result;
        if (s.empty() || t.empty())
            return result;

        unordered_map<char, int> map;       //record freq
        unordered_map<char, int> window;    //freq of letters in windows
        int minLength = INT_MAX;
        int fast = 0;
        int slow = 0;
        int currWindowLen = 0;
        for(int i = 0; i < t.size(); i ++)
            map[t[i]] ++;

        for(unordered_map<char,int>::iterator it=map.begin(); it!=map.end(); ++it)
            std::cout << it->first << " => " << it->second << '\n';


        for(; fast < s.size(); fast ++){
            char c = s[fast];
            if(map.find(c) != map.end()){ //if we this char in t
                window ++;             //increase freq in windows
                if(window <= map){
                    currWindowLen ++;       //if the just-seen letter can still be used to fill t
                }
            }

            if(currWindowLen >= t.size()){ //we have found a window
                //remove extra chars in the windows and move slow ptr forward
                //1.we have too much char
                //2.the slow is not even in the t.
                while(map.find(s[slow]) == map.end() ||  window[s[slow]] > map[s[slow]]){
                    window[s[slow]] --;
                    slow ++;
                }
                if(fast - slow + 1 < minLength){
                    minLength = fast - slow + 1;
                    result = s.substr(slow, minLength);
                }
            }

        }

        return result;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax