Minimum Window Subsequence

Minimum Window Subsequence mixes two-pointer scanning with a clever "match forward, then snap backward" move. It is a favorite because the obvious DP is heavy, but a tidy two-pass scan beats it for most inputs and is far easier to explain.

The slow way first

The textbook approach is dynamic programming: dp[i][j] = the start index of the smallest window of S[0..i] that contains T[0..j]. Filling that grid is O(|S| · |T|) time and space. It works, but it is a lot of bookkeeping for an interview whiteboard, and the space can hurt.

The question to ask: do I really need a 2-D table, or can I just walk the string? It turns out a two-pointer scan finds every candidate window directly.

The idea: match forward, then snap backward

Scan S left to right with hi, advancing a cursor through T each time the characters match. The moment the cursor reaches the end of T, every character of T has been covered somewhere in S[start..hi] — but start may be loose (there could be junk on the left). So we walk backward from hi, matching T in reverse, until the cursor empties. Wherever that backward walk stops is the tightest left edge lo.

After recording the window, restart the forward scan from lo + 1 so we never miss a later, possibly shorter, window.

Walk through it

Step through the animation. The hi pointer scans S and lights up b (index 1), d (index 3), e (index 4) — that completes T = "bde". Then lo starts at hi and walks left, matching e, d, skipping c, and finally b at index 1. The window S[1..4] = "bcde" is recorded as the best.

Pseudocode

best = ""
i = 0
while i is inside S:
    # forward: advance i, matching each char of T in order
    match T from its start by scanning forward; if T is not fully matched, stop
    hi = i                       # right edge of a valid window
    # backward: from hi, match T in reverse until T is consumed
    walk i left, consuming T from its end; stop when all of T is matched
    lo = i                       # tightest left edge
    if best is empty or window (lo..hi) is shorter:
        best = S[lo..hi]
    i = lo + 1                   # restart just past the left edge
return best

The Python solution

def min_window(S, T):
    best = ""
    i = 0
    while i < len(S):
        t = 0
        while i < len(S):
            if S[i] == T[t]:
                t += 1
                if t == len(T):
                    break
            i += 1
        if t < len(T):
            break
        hi = i
        t = len(T) - 1
        while t >= 0:
            if S[i] == T[t]:
                t -= 1
            i -= 1
        i += 1
        if best == "" or hi - i + 1 < len(best):
            best = S[i:hi + 1]
        i += 1
    return best

• The first inner while is the forward scan: it advances i and the T-cursor t, breaking the moment t == len(T) — meaning T is fully covered.
• if t < len(T): break handles the tail of S where T can no longer be completed — we are done.
• hi = i captures the right edge of this valid window.
• The second inner while is the backward walk: starting from hi, it consumes T from its last character backward. When it ends, i sits just before the tightest start, so i += 1 lands i exactly on lo.
• We compare hi - i + 1 (the window length) against the best so far and keep the shorter one; i += 1 restarts the forward scan one past the left edge.

Complexity

Both are the same big-O on paper, but the two-pointer scan uses only a couple of indices instead of a full grid, so it is far lighter in practice — and much easier to derive live.

When this pattern shows up

Practice