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"
If there is no such window in S that covers all characters in T, return the emtpy string
""
.
Minimum window is
"BANC"
.
Note:
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Solution:
string minWindow(string S, string T) {
string result = "";
int count =0;
int len = T.size();
int ToFind[256] = {0};
int Current[256] = {0};
for(int i=0;i<len;i++)
{
ToFind[T[i]]++;
}
int start = 0;
int rstart = 0;
int rend = S.size()-1;
for(int i=0;i<S.size();i++)
{
if(ToFind[S[i]]==0)
{
continue;
}
Current[S[i]]++;
if(Current[S[i]]<=ToFind[S[i]])
{
count++;
}
if(count == len)
{
while(ToFind[S[start]]==0||Current[S[start]]>ToFind[S[start]])
{
if(Current[S[start]]>ToFind[S[start]])
Current[S[start]]--;
start++;
}
int window = i - start +1;
if(window<rend- rstart+1)
{
rstart = start;
rend = i;
}
}
}
if(count==len)
result = S.substr(rstart, rend-rstart+1);
return result;
}
No comments:
Post a Comment