DSA Minimum Window Substring

The problem

Minimum Window Substring finds the shortest part of a text that contains every pattern letter with its needed count. A pattern with two copies of a letter needs two copies inside the window.

The answer is the window itself. An empty answer reports that no part of the text covers the pattern. Letters are case-sensitive, so a lowercase a never covers an uppercase A.

cases = [
    ("ADOBECODEBANC", "ABC", "BANC"),
    ("aa", "aa", "aa"),
    ("a", "aa", ""),
    ("ab", "b", "b"),
    ("a", "a", "a"),
]
for text, pattern, expected in cases:
    print("text", text, "pattern", pattern, "->", repr(expected))

The long case shrinks to four letters at the end of the text. The third case can never complete. Its text holds one a and its pattern needs two.

Intuition: test every substring

A first idea lists every substring of the text. A substring is a run of consecutive letters. The idea tests each run for full coverage of the pattern and keeps the shortest passing run.

The idea always finds the true answer. Its trap is the sheer count of substrings. A text of length n holds about n squared divided by two substrings, and each test costs its own scan.

text = "ADOBECODEBANC"
count = 0
for start in range(len(text)):
    for end in range(start, len(text)):
        count += 1
print("text length:", len(text))
print("substrings:", count)

Thirteen letters already hold 91 substrings. Doubling the text roughly quadruples the count. Most of those substrings share almost all their letters with a neighbour, and the naive test rescans them anyway.

Brute force: every substring tested for coverage

The brute force grows a substring from each start position. It counts the letters of the growing run. A run covers the pattern when every needed letter reaches its needed count.

The counter records every substring whose coverage was tested. No substring is skipped, however long it grows.

def covers(counts, need):
    for ch, n in need.items():
        if counts.get(ch, 0) < n:
            return False
    return True

def min_window_brute(text, pattern):
    if not pattern:
        return "", 0
    need = {}
    for ch in pattern:
        need[ch] = need.get(ch, 0) + 1
    best = ""
    tested = 0
    for start in range(len(text)):
        counts = {}
        for end in range(start, len(text)):
            counts[text[end]] = counts.get(text[end], 0) + 1
            tested += 1
            window = text[start:end + 1]
            if covers(counts, need) and (not best or len(window) < len(best)):
                best = window
    return best, tested

for text, pattern in [("ADOBECODEBANC", "ABC"), ("aa", "aa"), ("a", "aa")]:
    result, tested = min_window_brute(text, pattern)
    print(text, pattern, "->", repr(result), "substrings tested:", tested)

The brute force reaches the same answers. The long case pays 91 coverage tests for one answer. A text ten times longer would pay about a hundred times that.

The optimal solution: grow to cover, then shrink while complete

A sliding window is a run with a left edge and a right edge that only move forward. The need table counts each pattern letter once. The formed count tracks how many distinct letters currently meet their needed count.

The right edge grows the window until the formed count reaches the distinct letter count. The left edge then shrinks the window while it stays complete. Each complete window is a candidate, and the shortest candidate wins.

def min_window(text, pattern):
    if not pattern or not text:
        return ""
    need = {}
    for ch in pattern:
        need[ch] = need.get(ch, 0) + 1
    required = len(need)
    have = {}
    formed = 0
    left = 0
    best = ""
    for right, ch in enumerate(text):
        if ch in need:
            have[ch] = have.get(ch, 0) + 1
            if have[ch] == need[ch]:
                formed += 1
        while formed == required:
            window = text[left:right + 1]
            if not best or len(window) < len(best):
                best = window
            left_ch = text[left]
            if left_ch in need:
                if have[left_ch] == need[left_ch]:
                    formed -= 1
                have[left_ch] -= 1
            left += 1
    return best

cases = [
    ("ADOBECODEBANC", "ABC", "BANC"),
    ("aa", "aa", "aa"),
    ("a", "aa", ""),
    ("ab", "b", "b"),
    ("a", "a", "a"),
]
for text, pattern, expected in cases:
    result = min_window(text, pattern)
    print("text", text, "pattern", pattern, "->", repr(result), "match:", result == expected)

All five cases pass. Each letter enters the window once and leaves it at most once. No substring is ever rebuilt from scratch.

Walkthrough: ABAC with pattern ABC

The walk grows the right edge letter by letter. The state is the current window, its counts for needed letters, and the formed count. Shrinking starts the moment the window completes.

text = "ABAC"
need = {"A": 1, "B": 1, "C": 1}
have = {}
formed = 0
left = 0
for right, ch in enumerate(text):
    if ch in need:
        have[ch] = have.get(ch, 0) + 1
        if have[ch] == need[ch]:
            formed += 1
    print("window", text[left:right + 1], "counts", {k: have[k] for k in sorted(have)}, "formed:", formed)
    while formed == 3:
        print("complete, length", right - left + 1)
        left_ch = text[left]
        if left_ch in need:
            if have[left_ch] == need[left_ch]:
                formed -= 1
            have[left_ch] -= 1
        left += 1
        print("after shrink, window", text[left:right + 1], "formed:", formed)

The window completes at ABAC with a spare A at its left edge. Dropping that spare A keeps the window complete and shorter, so BAC becomes a candidate. The shrink tries one more step, and dropping B breaks coverage. The shrink stops there, and BAC stands as the shortest complete window seen.

Complexity

The brute force tests about n squared divided by two substrings for a text of length n, and each test scans its run, so its time grows far past O(n^2). The sliding window moves each edge at most n times, so its time is O(n).

The sliding window stores the need table and the window counts. Both hold at most one entry per distinct letter, so the extra space is O(1) in the size of the alphabet and never grows with the text.

for n in [13, 26, 52]:
    substrings = n * (n + 1) // 2
    print("text length", n, "- substrings:", substrings, " edge moves up to:", 2 * n)

Substring counts grow quadratically. Edge moves grow in a straight line. The window reuses the work of its previous position instead of restarting it.

Edge cases and pitfalls

An empty pattern asks for nothing. This article answers with an empty window by convention. A pattern longer than the text can never be covered, and the answer is empty as well.

def min_window(text, pattern):
    if not pattern or not text:
        return ""
    need = {}
    for ch in pattern:
        need[ch] = need.get(ch, 0) + 1
    required = len(need)
    have = {}
    formed = 0
    left = 0
    best = ""
    for right, ch in enumerate(text):
        if ch in need:
            have[ch] = have.get(ch, 0) + 1
            if have[ch] == need[ch]:
                formed += 1
        while formed == required:
            window = text[left:right + 1]
            if not best or len(window) < len(best):
                best = window
            left_ch = text[left]
            if left_ch in need:
                if have[left_ch] == need[left_ch]:
                    formed -= 1
                have[left_ch] -= 1
            left += 1
    return best

print("empty text:", repr(min_window("", "A")))
print("empty pattern:", repr(min_window("abc", "")))
print("pattern longer:", repr(min_window("ab", "abc")))
print("repeated letter need:", repr(min_window("aab", "aa")))
print("case matters:", repr(min_window("abc", "A")))
print("whole text needed:", repr(min_window("cba", "abc")))

The formed count is the classic pitfall. It must rise only when a letter count reaches its need exactly. Counting every needed letter added would mark the window complete too early, on spare copies alone.

Shrinking has the mirror pitfall. The formed count falls before the count drops below its need, not after. Reversing that order leaves a broken window marked complete, and the recorded answer can miss a required letter.