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.
class Solution { public: string minWindow(string S, string T) { // Start typing your C/C++ solution below // DO NOT write int main() function int ns=S.length(); int nt=T.length(); vector<int> need(256,0); vector<int> had(256,0); for(int i=0;i<nt;i++) { need[ T[i] ]++; had[ T[i] ]++; } int minLen=ns+100; int mStart=-1; int pre=0,nCount=nt; for(int i=0;i<ns;i++) { if (need[ S[i] ]> 0) { had[ S[i] ]--; if ( had[S[i]]>=0 ) nCount--; } if ( nCount ==0 ) { while( need[S[pre]]==0 || had[S[pre]]<0 ) { if ( need[S[pre]]>0 ) had[S[pre]]++; pre++; } if ( i-pre+1 <minLen ) { minLen=i-pre+1; mStart=pre; } } } if ( minLen==ns+100 ) return ""; else return S.substr(mStart,minLen); } };