[LeetCode] 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".

The basic idea is to find a window which contain all characters in T first, this window does not necessary to be optimize, and step by step, we try to optimize the window by deleting redundant characters.

Now I’ll use the given example to interpret this idea.

In string T, there is one ‘A’, one ‘B’, and one ‘C’, and these are what we need to find in S. (Current window is showed by underscore) We will use ‘winSize’ to record current window size, and ‘amount’ to record amount of character A, B, C in window.

First, we find a window which contain all characters in T,

ADOBEC ODEBANC          amount: 1, 1, 1     winSize: 6

now let’s try to optimize the window. Because there is no O, D, E in T, so we simply skip these 3 characters.

ADOBECODEB ANC                    amount: 1, 2, 1        winSize: 10

Because the lately found B is not the same character with window’s begin (A), so we add 1 in amount[B], and go on searching.

ADOBECODEBA NC                    amount: 2, 2, 1       winSize: 11

We found an ‘A’, so we can keep this A in window, and delete the former A, with all garbage characters behind A.

ADO BECODEBA NC        amount: 1, 2, 1    winSize: 8

There is two ‘B’s in window, and ‘B’ is begin of window, so we can delete the first ‘B’, garbage characters behind it as well.

ADOBE CODEBA NC        amount: 1, 1, 1    winSize: 6

Keep searching, skip ‘N’, we find ‘C’, which is same as window’s begin character, so we do same thing as we did.

ADOBECODE BANC         amount: 1, 1, 1    winSize: 4

Now we reach the end of string S, and 4 is the min window size, we return 4.

    string minWindow(string S, string T) {
        int needToFind[256] = {0};
        int hasFound[256] = {0};
        for(int i = 0; i < T.size(); ++i) {
            needToFind[T[i]]++;
        }
        int count = 0;
        int minWindowSize = INT_MAX;
        int start = 0, end = 0;
        string window;
        for(; end < S.size(); end++) {
            if(needToFind[S[end]] == 0) continue;
            hasFound[S[end]]++;
            if(hasFound[S[end]] <= needToFind[S[end]]) {
                count++;
            }
            if(count == T.size()) {
                while(needToFind[S[start]] == 0 ||
                    hasFound[S[start]] > needToFind[S[start]]) {
                    if(hasFound[S[start]] > needToFind[S[start]])
                        hasFound[S[start]]--;
                    start++;
                }
                if(end - start + 1 < minWindowSize) {
                    minWindowSize = end - start + 1;
                    window = S.substr(start, minWindowSize);
                }
            }
        }
        return window;
    }

🙂

 

This entry was posted in Algorithm, LeetCode and tagged , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*