76. Minimum Window Substring (Shortest Substring from Pangram)

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.

Thoughts:

1. "Do" Section keeps tracking "head" and "len" variable by "len"'s value
2. Count: # character current sliding window needs (does not have)
3. Very similar to 438. Find All Anagrams in a String

class Solution {

public:
    string minWindow(string s, string t) {
        if(t.length() > s.length()) return "";
        unordered_map <char, int> map;
        for(int i = 0; i < t.length(); i++ ){
            ++map[t[i]];
        }

        int left = 0, right = 0, head = INT_MAX, len = INT_MAX, count = map.size();

        while(right < s.length()){
            char rightChar = s[right];
            if(map.find(rightChar) != map.end()){
                if(--map[rightChar] == 0) count --;
            }
            right ++;
            while(count == 0){  // here we already find the window that contains the targeted substring
                // do 
               if(right - left < len){
                    head = left;
                    len = right - left;
                }

                // increment
                char leftChar = s[left];
                if (map.find(leftChar)!= map.end()){
                    if(++map[leftChar] > 0){
                        count++;
                    }
                }       
                left ++;
            }
        }

        if(len == INT_MAX) return "";
        return s.substr(head, len);
    }
};

Template: https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

Java Implementation: T: O(|S|), S:O(1)

class Solution {
    public String minWindow(String s, String t) {
        int [] map = new int [128];
        char [] chs = s.toCharArray();
        for(char c : t.toCharArray()){
            map[c]++;
        }

        int count = t.length(), slow = 0, fast = 0, head = 0, len = Integer.MAX_VALUE;

        while(fast < chs.length){
            if(map[chs[fast++]]-- > 0) count--;
            while(count == 0){
                if(fast - slow < len) {
                    len = fast - slow;
                    head = slow;
                }
                if(map[chs[slow++]]++ == 0) count++;
            }
        }

        return len == Integer.MAX_VALUE ? "": s.substring(head, head + len);
    }
}

string minWindow(string s, string t) {
        vector<int> map(128,0);
        for(auto c: t) map[c]++;
        int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
        while(end<s.size()){
            if(map[s[end++]]-->0) counter--; //in t
            while(counter==0){ //valid
                if(end-begin<d)  d=end-(head=begin);
                if(map[s[begin++]]++==0) counter++;  //make it invalid
            }  
        }
        return d==INT_MAX? "":s.substr(head, d);
    }

int findSubstring(string s){
        vector<int> map(128,0);
        int counter; // check whether the substring is valid
        int begin=0, end=0; //two pointers, one point to tail and one  head
        int d; //the length of substring

        for() { /* initialize the hash map here */ }

        while(end<s.size()){

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

            while(/* counter condition */){ 

                 /* update d here if finding minimum*/

                //increase begin to make it invalid/valid again

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

            /* update d here if finding maximum*/
        }
        return d;
  }

Python: https://leetcode.com/problems/minimum-window-substring/discuss/26804/12-lines-Python

def minWindow(self, s, t):
    need, missing = collections.Counter(t), len(t)
    i = I = J = 0
    for j, c in enumerate(s, 1):
        missing -= need[c] > 0
        need[c] -= 1
        if not missing:
            while i < j and need[s[i]] < 0:
                need[s[i]] += 1
                i += 1
            if not J or j - i <= J - I:
                I, J = i, j
    return s[I:J]

Java: https://leetcode.com/problems/minimum-window-substring/discuss/26805/Accepted-O(n)-solution

class Solution {
public:
    string minWindow(string S, string T) {
        if (S.empty() || T.empty())
        {
            return "";
        }
        int count = T.size();
        int require[128] = {0};
        bool chSet[128] = {false};
        for (int i = 0; i < count; ++i)
        {
            require[T[i]]++;
            chSet[T[i]] = true;
        }
        int i = -1;
        int j = 0;
        int minLen = INT_MAX;
        int minIdx = 0;
        while (i < (int)S.size() && j < (int)S.size())
        {
            if (count)
            {
                i++;
                require[S[i]]--;
                if (chSet[S[i]] && require[S[i]] >= 0)
                {
                    count--;
                }
            }
            else
            {
                if (minLen > i - j + 1)
                {
                    minLen = i - j + 1;
                    minIdx = j;
                }
                require[S[j]]++;
                if (chSet[S[j]] && require[S[j]] > 0)
                {
                    count++;
                }
                j++;
            }
        }
        if (minLen == INT_MAX)
        {
            return "";
        }
        return S.substr(minIdx, minLen);
    }
};