Minimum Window Substring (LeetCode 76)
You have two strings, s (length m) and t (length n). Find the shortest contiguous slice of s that contains every character of t, counting repeated characters as many times as they occur in t. If no slice of s qualifies, return the empty string "".
The test cases are built so that whenever an answer exists, it's unique.
Worked Examples
s = "ADOBECODEBANC", t = "ABC""BANC"s = "a", t = "a""a"s = "a", t = "aa"""⚖️Formal Constraints & Bounds
m == s.lengthn == t.length1 <= m, n <= 105sandtconsist of uppercase and lowercase English letters.
Core Insight
Tracking satisfied distinct character counts allows O(1) validity checking during window contractions.
Real-World Scenario & Production Applications
Full-text search highlighting (showing minimal context snippet containing all query terms), compiler syntax chunking.
Subproblems & Recurrence Decomposition3 Phases
Build character frequency map need from string t. Maintain have = 0 and required = len(need) to track fulfilled unique character requirements.
need = Counter(t)
required = len(need)
have = 0
window = {}Step-by-Step Execution Trace Table
right char | Window | matched | Action | Best Window |
|---|---|---|---|---|
| 'A'..'C' (idx 5) | "ADOBEC" | 3 / 3 (All matched) | Contract left past 'A' | "ADOBEC" (len 6) |
| 'O'..'C' (idx 10) | "CODEBA" | 3 / 3 (All matched) | Contract left | "ODEBANC" |
| 'N'..'C' (idx 12) | "BANC" | 3 / 3 (All matched) | Contract left | "BANC" (len 4) |
| 1 | need = Counter(t) |
| 2 | have = {} |
| 3 | matched = 0 |
| 4 | res = (inf, 0, 0) |
| 5 | left = 0 |
| 6 | for right in range(len(s)): |
| 7 | c = s[right] |
| 8 | have[c] = have.get(c, 0) + 1 |
| 9 | if c in need and have[c] == need[c]: |
| 10 | matched += 1 |
| 11 | while matched == len(need): |
| 12 | record the window if it is the shortest so far |
| 13 | remove s[left] from have (matched -= 1 if its count falls below need) |
| 14 | left += 1 |
| 15 | return best_substring |
Conceptual Narrative
A harder Sliding Window problem: the window tracks the count of every required character and shrinks whenever it can.
🧭 Conceptual Foundation & Pattern Intuition
In basic sliding window problems (like LC 209 or LC 3), the condition to expand or shrink depends on a scalar sum or a simple set of unique characters. In Minimum Window Substring (LC 76), the window must contain every character from string t with at least the frequency specified in t.
Checking whether the current window contains all required frequencies naively takes time on every step. Over a string of length , that would degrade performance to . The algorithmic breakthrough is Dual-State Frequency Tracking:
- A frequency map
needstoring required counts for each character int. - A running frequency map
havefor characters in the active window. - A scalar counter
matched: tracks how many unique characters inthave reached their required frequency threshold (have[c] == need[c]).
When matched == len(need), the window is unconditionally valid! You record the candidate length and greedily contract from the left to find the tightest possible valid substring.
🛒 The Analogy: The Grocery Shopping Checklist
Imagine you have a shopping list (t): you need 3 Apples, 2 Bananas, and 1 Carrot. You walk down a superstore aisle (s) tossing produce into your cart (right pointer):
- When you pick up your 3rd Apple, you cross "Apples" off your checklist (
matched += 1). - Picking up a 4th Apple doesn't check off any new item—it's just a surplus.
- Once every item on your checklist is crossed off (
matched == len(need)), your cart is valid! - Now, can you trim items from the start of your aisle run (
leftpointer) to make your shopping trip as short as possible? You put items back onto shelves from the front. If you put back an orange (not on list) or a surplus apple (still leaving 3 in cart), your checklist is still complete! Only when you put back an essential item so its count falls below the required threshold (have[c] < need[c]) do you uncheck that item (matched -= 1) and resume walking forward.
🔑 The Key Idea in the Code
Because each character is visited at most twice (once by right, once by left), the entire algorithm executes in strict linear time.
Comparing character count dictionaries on each step: Comparing frequency maps of size 128 takes O(128) per iteration. Use a
matchedcount of unique characters to achieve strictO(1)step transitions.Prematurely decrementing matched count: When shrinking
left, only decrementmatched -= 1whenwindow[char] < target[char]. Ifwindow[char]was exceedingtarget[char], removing it does not break validity.Off-by-one in substring slice: When storing the best window
[start, min_len], the return slice in Python iss[start : start + min_len], nots[start : min_len].
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Shortest substring containing all characters of a target string with character multiplicity.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: matched counter increments only when have[c] == need[c]; window is valid when matched == len(need).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to decrement
matchedwhen an evicted character count drops belowneed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I count required character frequencies in t and use a matched scalar counter. I expand right adding characters to have; when have[c] reaches need[c], matched increments. When matched == len(need), I shrink left, recording the minimum window. Runs in
O(N)time andO(1)auxiliary space."
Complexity & Mathematical Proof
O(N + M)
Look at the execution steps: Counts target characters in T (length M). Right pointer expands over S (length N) satisfying required character counts; left contracts window while still valid. Total 2N pointer advances.
O(|Sigma|) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Frequency maps for target characters and active window bounded by character set size Sigma.
T(N, M) = O(M) + O(2N) = O(N + M)
Derivation Progression
O(M) over string T
Builds frequency map of required characters in T of length M.
R advances N times
Adds characters to window map and increments formed counter when count matches requirement.
L advances at most N times
Shrinks window from left while maintaining formed == required condition, updating shortest valid window.
Variable Definitions
Length of source string s
Length of target string t
Character set size (at most 128 ASCII characters)
Memory Architecture & Bounds
O(1) Iterative
O(|Sigma|) Two character frequency tables (at most 128 ASCII entries)
O(K) Substring slice where K <= N
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "smallest substring covering every character of t, duplicates and all". Variable sliding window with multiset coverage tracking.
. Time budget strictly linear . Space .
Duplicate character matching: increment have only when window_freq[c] == t_freq[c], not on every occurrence. Decrement have only when window_freq[c] < t_freq[c] during contraction. No valid window exists (return "").
Minimum Window Substring (LeetCode 76)
You have two strings, s (length m) and t (length n). Find the shortest contiguous slice of s that contains every character of t, counting repeated characters as many times as they occur in t. If no slice of s qualifies, return the empty string "".
The test cases are built so that whenever an answer exists, it's unique.
Worked Examples
s = "ADOBECODEBANC", t = "ABC""BANC"s = "a", t = "a""a"s = "a", t = "aa"""⚖️Formal Constraints & Bounds
m == s.lengthn == t.length1 <= m, n <= 105sandtconsist of uppercase and lowercase English letters.
Core Insight
Tracking satisfied distinct character counts allows O(1) validity checking during window contractions.
Real-World Scenario & Production Applications
Full-text search highlighting (showing minimal context snippet containing all query terms), compiler syntax chunking.
Subproblems & Recurrence Decomposition3 Phases
Build character frequency map need from string t. Maintain have = 0 and required = len(need) to track fulfilled unique character requirements.
need = Counter(t)
required = len(need)
have = 0
window = {}Step-by-Step Execution Trace Table
right char | Window | matched | Action | Best Window |
|---|---|---|---|---|
| 'A'..'C' (idx 5) | "ADOBEC" | 3 / 3 (All matched) | Contract left past 'A' | "ADOBEC" (len 6) |
| 'O'..'C' (idx 10) | "CODEBA" | 3 / 3 (All matched) | Contract left | "ODEBANC" |
| 'N'..'C' (idx 12) | "BANC" | 3 / 3 (All matched) | Contract left | "BANC" (len 4) |
| 1 | need = Counter(t) |
| 2 | have = {} |
| 3 | matched = 0 |
| 4 | res = (inf, 0, 0) |
| 5 | left = 0 |
| 6 | for right in range(len(s)): |
| 7 | c = s[right] |
| 8 | have[c] = have.get(c, 0) + 1 |
| 9 | if c in need and have[c] == need[c]: |
| 10 | matched += 1 |
| 11 | while matched == len(need): |
| 12 | record the window if it is the shortest so far |
| 13 | remove s[left] from have (matched -= 1 if its count falls below need) |
| 14 | left += 1 |
| 15 | return best_substring |
Conceptual Narrative
A harder Sliding Window problem: the window tracks the count of every required character and shrinks whenever it can.
🧭 Conceptual Foundation & Pattern Intuition
In basic sliding window problems (like LC 209 or LC 3), the condition to expand or shrink depends on a scalar sum or a simple set of unique characters. In Minimum Window Substring (LC 76), the window must contain every character from string t with at least the frequency specified in t.
Checking whether the current window contains all required frequencies naively takes time on every step. Over a string of length , that would degrade performance to . The algorithmic breakthrough is Dual-State Frequency Tracking:
- A frequency map
needstoring required counts for each character int. - A running frequency map
havefor characters in the active window. - A scalar counter
matched: tracks how many unique characters inthave reached their required frequency threshold (have[c] == need[c]).
When matched == len(need), the window is unconditionally valid! You record the candidate length and greedily contract from the left to find the tightest possible valid substring.
🛒 The Analogy: The Grocery Shopping Checklist
Imagine you have a shopping list (t): you need 3 Apples, 2 Bananas, and 1 Carrot. You walk down a superstore aisle (s) tossing produce into your cart (right pointer):
- When you pick up your 3rd Apple, you cross "Apples" off your checklist (
matched += 1). - Picking up a 4th Apple doesn't check off any new item—it's just a surplus.
- Once every item on your checklist is crossed off (
matched == len(need)), your cart is valid! - Now, can you trim items from the start of your aisle run (
leftpointer) to make your shopping trip as short as possible? You put items back onto shelves from the front. If you put back an orange (not on list) or a surplus apple (still leaving 3 in cart), your checklist is still complete! Only when you put back an essential item so its count falls below the required threshold (have[c] < need[c]) do you uncheck that item (matched -= 1) and resume walking forward.
🔑 The Key Idea in the Code
Because each character is visited at most twice (once by right, once by left), the entire algorithm executes in strict linear time.
Comparing character count dictionaries on each step: Comparing frequency maps of size 128 takes O(128) per iteration. Use a
matchedcount of unique characters to achieve strictO(1)step transitions.Prematurely decrementing matched count: When shrinking
left, only decrementmatched -= 1whenwindow[char] < target[char]. Ifwindow[char]was exceedingtarget[char], removing it does not break validity.Off-by-one in substring slice: When storing the best window
[start, min_len], the return slice in Python iss[start : start + min_len], nots[start : min_len].
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Shortest substring containing all characters of a target string with character multiplicity.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: matched counter increments only when have[c] == need[c]; window is valid when matched == len(need).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to decrement
matchedwhen an evicted character count drops belowneed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I count required character frequencies in t and use a matched scalar counter. I expand right adding characters to have; when have[c] reaches need[c], matched increments. When matched == len(need), I shrink left, recording the minimum window. Runs in
O(N)time andO(1)auxiliary space."
Complexity & Mathematical Proof
O(N + M)
Look at the execution steps: Counts target characters in T (length M). Right pointer expands over S (length N) satisfying required character counts; left contracts window while still valid. Total 2N pointer advances.
O(|Sigma|) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Frequency maps for target characters and active window bounded by character set size Sigma.
T(N, M) = O(M) + O(2N) = O(N + M)
Derivation Progression
O(M) over string T
Builds frequency map of required characters in T of length M.
R advances N times
Adds characters to window map and increments formed counter when count matches requirement.
L advances at most N times
Shrinks window from left while maintaining formed == required condition, updating shortest valid window.
Variable Definitions
Length of source string s
Length of target string t
Character set size (at most 128 ASCII characters)
Memory Architecture & Bounds
O(1) Iterative
O(|Sigma|) Two character frequency tables (at most 128 ASCII entries)
O(K) Substring slice where K <= N
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "smallest substring covering every character of t, duplicates and all". Variable sliding window with multiset coverage tracking.
. Time budget strictly linear . Space .
Duplicate character matching: increment have only when window_freq[c] == t_freq[c], not on every occurrence. Decrement have only when window_freq[c] < t_freq[c] during contraction. No valid window exists (return "").