Minimum Window Substring

Given two strings s and t, return the smallest substring of s that contains all characters of t (including duplicates). If no such substring exists, return the empty string.

A brute force check of all substrings is too slow. A sliding window with character counts solves it in O(n).

Why this is worth learning

A target is a multiset of required occurrences, not a set of distinct letters. Once a window covers it, shrinking is how you discover the shortest candidate for that endpoint.

Before coding: one-minute experiment

For s="ABAAC" and t="AAC", why is "AC" not a valid answer, and what is?

Function signature

func MinWindow(s string, t string) string

Inputs / outputs

• s: source string.
• t: target string (may contain duplicates).
• Return: the minimum window substring, or "" if none.

Example

s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Constraints

• 0 <= len(s), len(t) <= 100_000

Core idea (near-solution)

Use a sliding window with counts:

• need[c]: the fixed target multiplicity of byte c; window[c] separately records the current count. The reference does not decrement need.
• formed: how many distinct characters have been satisfied.
• required: number of distinct characters in t.

Invariant: when formed == required, the current window contains all required characters (including duplicates). Then shrink from the left to minimize it.

Algorithm (step-by-step)

1. If t or s is empty, return "" before entering a shrink loop. Otherwise build target counts and set required to the number of distinct required bytes.
2. Initialize l = 0, formed = 0, and a map window.
3. Expand r from 0 to len(s)-1:
   • Add s[r] to window.
   • If this byte is required and its count has just reached its target count, increment formed. Surplus copies do not increment it again.
   • While formed == required:
     • Update best window if this one is smaller.
     • Remove s[l] from window and increment l.
     • If a required count falls below the needed amount, decrement formed.
4. Return the best window found or "".

Correctness sketch

The window counts always equal the byte multiplicities between left and right. formed counts target byte kinds whose required multiplicity is met, not total matched bytes. Extending can make a kind satisfied only when its count reaches the requirement. While every kind is satisfied, record the current candidate and remove the left byte; a kind becomes unsatisfied only when its count drops below its requirement. This explores the shortest valid window for each relevant endpoint. A discarded start already produced a valid window and any later extension from that start would be longer, so it never needs to return. The best recorded valid substring is therefore minimal.

Trace (hand walkthrough)

s = "ADOBECODEBANC", t = "ABC"
- right=5 ('C'): [0,5] = "ADOBEC" first covers A,B,C; best length 6
- remove index 0 ('A'): formed drops to 2; left=1
- right=10 ('A'): coverage returns; shrink past D,O,B,E
- [5,10] = "CODEBA" ties length 6; keep the earlier best
- remove C at 5: formed drops to 2; left=6
- right=12 ('C'): shrink "ODEBANC" → "DEBANC" → "EBANC" → "BANC"
- record [9,12], length 4, before removing B; return "BANC"

Pitfalls to avoid

• Ignoring duplicate counts in t (must match multiplicities).
• Shrinking before verifying the window is valid.

Debugging lens

Test duplicate target bytes, no match, empty target, and tied minimum lengths. The reference updates only for a strictly shorter result, preserving the earliest minimum encountered.

Complexity

Time: O(len(s)+len(t)) using the reference's two fixed 256-entry arrays. Auxiliary space: O(1) for the byte alphabet. The result is a substring of s; its storage can share s's bytes.

Implementation notes (Go)

• Track counts for target characters and a formed counter.
• Shrink while valid to minimize length; record best window indices.

Contract precision

Matching uses bytes and their multiplicities. Empty t returns an empty string. Ties retain the earliest minimum-length window in the supplied implementation.

Reconstruction checkpoint

For s="ABAAC" and t="AAC", why is "AC" not a valid answer, and what is?

Return to Sliding Window · Module quiz