Leetcode: Minimum Window Substring

 This question is asked at Facebook, Amazon, Microsoft, and many other companies. It is as follows:

Given 2 strings s and t, return the minimum window in s which will contain all characters in t. If there is no such window in s that covers all characters in t, return empty string "". I'm thinking this is a dynamic programming (DP) problem, but my opinion could be subject to change. Here are some examples:

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Example 2:

Input: s = "a", t = "a"

Output: "a", 

and we want to find an algorithm that runs in O(n) time. How do we do this? We actually have a template for substring windows.

First we use two pointers: A start pointer and the end pointer in order to represent a window.

Then, we move to the end to find a valid window. When a valid window is found, move start to find a smaller window. To check if a window is valid, use a map to store the char, count for all the characters in a string. 

There, as a result, should be a hashmap with 2 assisted pointers.

Here are 2 versions of this:

C++:

int findSubstring(string s) {

    vector<int> map(128, 0); 

    int counter; //check whether a substring is valid

    int begin = 0; end = 0; //one tail pointer and one head pointer

    int d; //substring length 

    for() {/*initialize hashmap*/}

    while(end < s.size()){

        if(map[s[end++]]-- ?) {/*modify counter here*/ }

        while(/*some counter condition*/) {

            /*update the d if we found the minimum*/

            /*increase the location of begin*/

            if(map[s[begin++]]++ ?){/* modify counter here*/}

        }

    }

    return d;

}

Java:

public String minWindow(String s, String t) {

    int[] map = new int[128];

    int start = 0, end = 0, d; //d is the length of the substring

    //initialize minstart/minend/counter/minlength etc. or you can do this for max too.

    for(char c : t.toCharArray()) {//initialize hashmap

        map[c]++;

    }

    while(end < s.length()) {

        final char c1 = s.charAt(end);

        if(map[c1] > 0) //modify the counter here;

        map[c1]--;

        end++;

        while(some counter condition) {

            if(we found a minimum length){

                //update the minimum length

                //update the minimum start as well to the new start value

                final char c2 = s.charAt(start);

                map[c2]++;

                if(map[c2] > 0) //update counter

                start++;

            }

        }

    }

}

We should update the maximum when asked to find the maximum substring, and update the minimum when asked to find the minimum substring. In C++ you can modify several pointers within a line in the same command, but you need to be very careful with that. 

And here is the final code in C++:

   string minWindow(string s, string t) {

        //intialize map

        vector<int> map(128, 0);

        //add string frequencies inside of the hashmap

        for(auto c: t) map[c]++;

        //initialize counter, begin of string, end of string, length of string, and head beginning pointer

        int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;

        //loop until you reach the end of the string 

        while(end < s.size()){

            //decrement the counter if the word contains this string.

            if(map[s[end++]] -->0) counter--;

            //if the string contains everything in string t

            while(counter == 0) {

                //If the length is the minimum length, update the length

                if(end - begin < d) d = end - (head = begin);

                //update this beginning string again, now that we start here. the previous indices don't need to be updated since we're not accessing them. 

                if(map[s[begin++]]++==0) counter++;

            }

        }

        return d == INT_MAX? "": s.substr(head, d);

   }

And in Java:

public String minWindow(String s, String t) {

    //intialize map

    int[] map = new int[128];

    //add string frequencies inside of the hashmap

    for(char c : t.toCharArray()){

        map[c]++;

    }

     //initialize counter, begin of string, end of string, length of string, and head beginning pointer

    int start = 0, end = 0, minStart = 0, minLen = Integer.MAX_VALUE, counter = t.length();

    //loop until you reach the end of the string 

    while(end < s.length()) { 

        final char c1 = s.charAt(end); 

        //decrement the counter if the word contains this string.

        if(map[c1] > 0) counter--;

        map[c1]--;

        end++;

        //if the string contains everything in string t

        while(counter == 0) {

            //If the length is the minimum length, update the length

            if(minLen > end - start) {

                minLen = end - start;    

                minStart = start;

            }

            //update this beginning string again, now that we start here. the previous indices don't need to be updated since we're not accessing them. 

            final char c2 = s.charAt(start);

            map[c2]++;

            if(map[c2] > 0) counter++;

            start++;

        }

    }

    //return length of minimum if it exists, else return the empty string. 

    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);

}

This is a demonstration on what the diagram of this question looks like: