Thursday, May 16, 2013

Leetcode: Minimum Window Substring in C++



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