## 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);
}
};

#### 1 comment:

1. check out my solution, clearer and better than yours :)
string minWindow(string S, string T) {
map counter;

map::iterator>> c;
list queue;
int remaining = T.length();
int minimumLength = INT_MAX;
string retValue = "";
for (char t : T) {
if (counter.count(t) == 0) {
counter.insert(pair(t, 0));
}
counter[t]++;
}
for (int j = 0; j < S.length(); j++) {
if (counter.count(S[j]) != 0) {
int i = counter[S[j]];
if (i == 0) {
auto i = c.at(S[j]).front();
queue.erase(i);
c.at(S[j]).pop();
} else {
counter[S[j]]--;
remaining--;
}
queue.push_back(j);
c[S[j]].push(--queue.end());
if (remaining == 0 && j - queue.front() < minimumLength) {
minimumLength = j - queue.front();
retValue = S.substr(queue.front(), minimumLength + 1);
}
}
}
return retValue;
}