Minimum Window Substring

HARD✓ CHIP-TIMEDLC #76 — FULL STATEMENT ↗

The drill: Somewhere in string s hides the shortest stretch containing every character of t, duplicates included — find it, or report that nothing qualifies. The defining workout for expand-and-contract windows: counts decide when a window is legal, and legality lets the left edge chase the right.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two strings arrive, s and t. Somewhere inside s there may exist a contiguous stretch that contains every character of t, with duplicates matched at least as many times as they appear in t.

The job is to find the shortest such stretch and hand it back exactly as it appears in s. If no stretch of s covers every character of t, the answer is an empty string instead.

Order inside the window doesn't matter — only that the required character counts are all met simultaneously. Multiple windows can tie for shortest; any one of them is an acceptable answer.

EX 01

s = "xayzbca" · t = "abc"

→ "bca"

THE TIGHT WINDOW SITS AT THE TAIL

EX 02

s = "abaxab" · t = "aab"

→ "aba"

DUPLICATES IN T MUST ALL BE COVERED

EX 03

s = "aa" · t = "aaa"

→ ""

T LONGER THAN S — IMPOSSIBLE

s and t each range from a single character to a few thousand
t's characters can repeat, and the window must cover every repeat
an empty string signals no covering window exists
any window tied for shortest is an acceptable answer

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking every substring recounts the same letters thousands of times. A window that slides one step can inherit its own bookkeeping — what, exactly, needs to carry over?

HINT 2 THE STRUCTURE

March the right edge forward until the window covers t, then pull the left edge in while coverage survives. Both edges only ever move forward, so the sweep is linear.

HINT 3 ONE STEP FROM THE ANSWER

Keep per-character need counts plus one number, missing. The right edge decrements a need — missing drops only if that need was positive. The left edge increments it back — missing rises when a need turns positive. Snapshot the window every time missing is zero.

COACH'S BOARD — THE PATTERN, STEP BY STEP

EXPAND, THEN CHASE IT SHUTPATTERN · SLIDING WINDOW — VARIABLE WIDTHs = "xayzbca" · t = "abc"

NEED (a,b,c) · MISSING

— empty —

STEP 1

t = "abc" needs one each of a, b, c. Missing starts at 3 — expand right until missing hits 0, then contract left while it stays 0.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/minimum-window-substring.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""
        need = collections.Counter(t)
        missing = len(t)          # required characters not yet inside the window
        best_lo, best_hi = 0, -1  # best window seen; hi < lo means none yet
        lo = 0
        for hi, c in enumerate(s):
            if need[c] > 0:
                missing -= 1
            need[c] -= 1
            while missing == 0:   # window is legal — contract from the left
                if best_hi < 0 or hi - lo < best_hi - best_lo:
                    best_lo, best_hi = lo, hi
                left = s[lo]
                need[left] += 1
                if need[left] > 0:  # that character just broke coverage
                    missing += 1
                lo += 1
        return s[best_lo:best_hi + 1]

TIME O(N + M)SPACE O(1)PYTHON · RACE PACE · 21 LN

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)
        best = ""
        for i in range(len(s)):
            remaining = dict(need)
            missing = len(t)
            for j in range(i, len(s)):
                c = s[j]
                if remaining.get(c, 0) > 0:
                    missing -= 1
                remaining[c] = remaining.get(c, 0) - 1
                if missing == 0:  # first cover from this anchor is its shortest
                    if not best or j - i + 1 < len(best):
                        best = s[i:j + 1]
                    break
        return best

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 17 LN

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        int missing = t.length(); // required characters not yet inside the window
        int bestLo = 0, bestLen = Integer.MAX_VALUE;
        int lo = 0;
        for (int hi = 0; hi < s.length(); hi++) {
            char c = s.charAt(hi);
            if (need[c] > 0) missing--;
            need[c]--;
            while (missing == 0) { // window is legal — contract from the left
                if (hi - lo + 1 < bestLen) {
                    bestLen = hi - lo + 1;
                    bestLo = lo;
                }
                char left = s.charAt(lo);
                need[left]++;
                if (need[left] > 0) missing++; // that character just broke coverage
                lo++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestLo, bestLo + bestLen);
    }
}

TIME O(N + M)SPACE O(1)JAVA · RACE PACE · 26 LN

class Solution {
    public String minWindow(String s, String t) {
        int[] need = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        String best = "";
        for (int i = 0; i < s.length(); i++) {
            int[] remaining = need.clone();
            int missing = t.length();
            for (int j = i; j < s.length(); j++) {
                char c = s.charAt(j);
                if (remaining[c] > 0) missing--;
                remaining[c]--;
                if (missing == 0) { // first cover from this anchor is its shortest
                    if (best.isEmpty() || j - i + 1 < best.length()) {
                        best = s.substring(i, j + 1);
                    }
                    break;
                }
            }
        }
        return best;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 23 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED