76. 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 empty string "".

My accepted code can be found here

It’s a IQ quiz problem. The basic idea of this question is first we find a legit window in S that contains all characters of T. Then we shrink the window to a smallest one. Then we try to find another window and do the same thing, and record the smallest among all windows.

All of the steps are not difficult at all to implement, but the idea and algorithm looks very tricky.

We first preprocess a target table, which contains the numbers of each character required in the window.

And then we assign a fast pointer going through the string S, it decrement the count of every character it met, until all character required in the table are met.

Then we start to shrink the window from start by assigning a pointer slow, which increment itself whenever it meets a unnecessary character. And we remember the interval [slow, fast] when the slow pointer stop.

Then we kick one necessary character from the start, then restart the fast pointer.

The full algorithm comes as follow:

MinimalWindow(s: string, t: string): string:
    let table = a mapping that maps character to integer
    initialize table, so that table[char] = count(t, char)
    let rest = length(t)

    let head = 0, rear = positive infinity
    let slow = 0
    for fast = 0 until length(s):
        if table[s[fast]] > 0:
            rest -= 1
        table[s[fast]] -= 1
        if rest == 0:
            for slow = slow until fast, and table[s[slow]] < 0:
                ++table[s[slow]]
            if fast - slow < rear - head:
                head, rear = slow, fast
            ++rest
            ++table[s[slow]]
    if rear == positive infinity:
        return ""
    return s[head to rear]

The time complexity is O(n) with respect to the length of s, since slow and fast traverse the string only once.