Problem Overview
LeetCode 76 — Minimum Window Substring — gives you two strings s and t. Return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such window exists, return "".
For example, s = "ADOBECODEBANC", t = "ABC". The minimum window is "BANC" (indices 9-12). It contains A, B, and C. Shorter windows like "CODEBA" contain the characters but are longer than "BANC".
This is the hardest sliding window problem on LeetCode and one of the most frequently asked in interviews. The key technique is the expand-then-shrink pattern: grow the window until all characters are satisfied, then shrink from the left to find the minimum.
- Input: strings s (source) and t (target)
- Find the smallest substring of s containing all chars of t
- Duplicates in t must be covered (if t has 2 A's, window needs 2 A's)
- Return "" if no valid window exists
- The answer is guaranteed to be unique
Sliding Window with Frequency Maps
Build a frequency map need from t: count each character's required occurrences. Initialize a window frequency map have (empty). Use two pointers left = right = 0. Track two counters: required = number of unique characters in t, and formed = number of characters whose window count meets the required count.
Expand: move right forward, adding s[right] to have. If have[s[right]] equals need[s[right]], increment formed. When formed equals required, the window contains all characters of t.
Shrink: while formed equals required, try to minimize the window. Record the window if it is the smallest seen. Remove s[left] from have. If have[s[left]] drops below need[s[left]], decrement formed. Move left forward. Continue expanding after shrinking breaks the condition.
Formed vs Required
Required counts unique characters in t (e.g., t="ABA" has required=2 for A and B). Formed tracks how many of those unique chars have met their frequency requirement. When formed == required, the window is valid. This avoids comparing entire maps each step.
Step-by-Step Walkthrough
Consider s = "ADOBECODEBANC", t = "ABC". need = {A:1, B:1, C:1}, required = 3. Expand right: A(formed=1), D, O, B(formed=2), E, C(formed=3). Window "ADOBEC" is valid. Record length 6, start 0.
Shrink left: remove A, have[A]=0 < need[A]=1, formed=2. Stop shrinking. Window broke. Continue expanding: O, D, E, B, A(formed back to 3 via A count). Window "CODEBA" length 6. Shrink: remove C, formed=2. Stop.
Continue expanding: N, C(formed=3). Window "BANC" length 4. Shrink: remove B, formed=2. Stop. No more chars to expand. Best window: "BANC" length 4. This is the minimum window containing all of A, B, C.
Optimization: Filtered Index List
When s is much longer than t and has many irrelevant characters, you can precompute a filtered list of (index, char) pairs containing only characters that appear in t. The sliding window operates on this filtered list instead of the full string.
For example, if s = "XXXXAXXXXBXXXXC" and t = "ABC", the filtered list is [(4,A), (9,B), (14,C)]. The window slides over 3 elements instead of 15. The window boundaries still reference the original string indices for substring extraction.
This optimization does not change the worst-case complexity but significantly improves performance when s has many characters not in t. In practice, it can be 2-5x faster for long strings with sparse target characters.
When to Use Filtered Approach
If len(t) is much smaller than len(s) and s has many non-target characters, filtering helps. If most characters in s appear in t, filtering adds overhead without benefit. Profile both approaches for your specific input distribution.
Implementation in Python and Java
Python: from collections import Counter. need = Counter(t). have = {}. required = len(need). formed = 0. ans = (float("inf"), 0, 0). left = 0. For right, c in enumerate(s): have[c] = have.get(c, 0) + 1. If c in need and have[c] == need[c]: formed += 1. While formed == required: update ans. have[s[left]] -= 1. If s[left] in need and have[s[left]] < need[s[left]]: formed -= 1. left += 1.
Java: use int[] for character frequencies (size 128 for ASCII). Same expand-shrink logic. Track minLen and minStart. Return s.substring(minStart, minStart + minLen) or "" if no valid window found.
Both implementations are about 25 lines. The Python version is more readable due to Counter and dictionary operations. The Java version is faster due to array-based frequency counting.
Complexity Analysis
Time complexity is O(|s| + |t|). Building the need map is O(|t|). The sliding window processes each character at most twice (once when right expands, once when left shrinks). Total: O(2|s| + |t|) = O(|s| + |t|).
Space complexity is O(|s| + |t|). The need and have maps each hold at most 128 entries (ASCII characters). The output substring takes O(|s|) in the worst case. If using the filtered approach, the filtered list takes O(|s|) additional space.
This is optimal — we must read every character in s at least once, and we must read t to know the target. The amortized O(1) per character (each is processed at most twice by the window) is the best possible.
YeetCode Flashcard Tip
Minimum Window Substring is the gold standard for sliding window problems. Practice it alongside Longest Substring Without Repeating Characters and Fruit Into Baskets on YeetCode to master the expand-shrink pattern.