leetcode Question 57: Minimum Window Substring

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 emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Analysis:

Generally speaking, the idea of this problem is not straightforward, implementation is not easy, it is a difficult problem!!!

The idea is like this:
   We have two pointers, p and q.  S[p:q] stores the string covers all the chars in T. We want minimum p:q.
   Start from the whole S, p=0, q=S.size()-1,  if it cannot cover T, return "";
   Fix p, try to move q close to p, but keep the requirement S[p:q] covers T.
   Find the shortest p:q, here exactly is 1:q, where S[1:q] covers T.
   Move p and q dynamically:
        if  S[p] is irrelevant char, p++;
        if  S[p] is char in T, must move q to left until find S[q]==S[p] to keep the requirement, or q is last.
            When move q to left, if S[q] is in T, store the S[q] occurrence.
   Every move, compare the length p:q store the minimum length and position.

 
   To check if the S[p:q] covers T, because the complexity requirement, the idea goes as follows:
   (1)  use map<char, int>,  to store the occurrence of chars in S and T. Be careful with the duplicate case.
   (2)  Check the occurrence of mapS and mapT, if mapS[T[i]]<mapT[T[i]], return false;
    After find the first covered string [1:q], we do like one-by-one move, so the cover test can only be the occurrence of the first char S[p], and when move q, don't forget add occurrence if meets S[q] in T.

 
See code below for more  details. Both small and large tests are passed

Code(201309):

class Solution {
public:
    string minWindow(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (S.size()<T.size()){return "";}
            
        map<char,int>mp; // store chars occurrence of T 
        for(int i=0;i<T.size();i++){mp[T[i]]++;}
        
        int res_len=INT_MAX; // result length
        int res_p=0;//result start posiion
        
        int p=0; //pointer start
        int q=S.size()-1; //pointer end
        
        while (mp[S[p]]==0){if(p>=S.size()){return "";} p++;} //remove irralevent starting chars
        while (mp[S[p]]==0){q--;if(q<0){return "";}} // remove irralevent ending chars
        
        map<char,int> tab; //store chars occurrence of S[p:q]
        for (int i=p;i<=q;i++){tab[S[i]]++;} 
                    
        while (tab[S[q]]>mp[S[q]] || mp[S[q]]==0){ // move q to left find the 1st covered substring
           tab[S[q]]--;
           q--;
        }
            
        for (int i=0;i<T.size();i++){  // if no covered substring found, return ""
            if (tab[T[i]]<mp[T[i]]){return "";}
        }
    
        if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
        
        
        while (p<q){
            if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
            if (mp[S[p]]==0){p++;continue;} // if current char is not in T, go next
            if (tab[S[p]]>mp[S[p]]){tab[S[p]]--;p++;continue;} // if more chars in this substring, go next
            
            q++; 
            while (q<S.size() && S[q]!=S[p]){ if (mp[S[q]]>0){tab[S[q]]++;} q++;} //move q to find a substring covers T
            if (q>=S.size()){q=S.size()-1;}else{tab[S[q]]++;}
            
            if (S[q]==S[p]){ tab[S[p]]--; if (tab[S[p]]<mp[S[p]]){break;} p++;continue;}        
            break;
        }
        
        return S.substr(res_p,res_len);
    }
};