Sliding Window · LC #76
Minimum Window Substring
Variable sliding window with a "have/need" counter: expand right to satisfy all character requirements, then greedily shrink from left while still satisfied. The hardest and most general sliding-window template.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given strings `s` and `t`, return the minimum window substring of `s` that contains all characters of `t` (including duplicates). Return `""` if impossible.
Sample I/O
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Input: s = "a", t = "aa" Output: ""
Time: O(|s|+|t|) · Space: O(|t|)
Intuition
How to Think About It
Intuition
Use two counters: need (frequency of each char in t) and window (frequency of current window in s). Track have = number of distinct characters in t whose count in window matches or exceeds need. When have == required (all characters satisfied), try shrinking from the left to find a smaller valid window.
Core Concept
Build need map from t. have=0, required=len(need). Expand r: add s[r] to window; if window[s[r]] == need[s[r]] increment have. While have == required: record if window is smallest; remove s[l] from window; if window[s[l]] < need[s[l]] decrement have; advance l. Time O(|s| + |t|), Space O(|t| + charset).
When to use
Any "minimum window containing all required elements" problem. Generalises to minimum window with at-most/exactly-k constraints by adjusting the have/need tracking logic.
When NOT to use
When the window must contain elements in order (need a different DP/pointer approach). When t has no characters in s (early return empty string). When s is shorter than t.
Key Insights
What to Know Cold
- Tracking have/required avoids O(|charset|) map comparison per step - have increments only when a character's count exactly meets the need.
- Shrink as far as possible while valid (while have == required) to find the minimum window.
- The have counter decrements only when removing a character causes its window count to drop below its need count.
- Store result as (start, length) not the substring itself to avoid O(n) string slicing per step.
- This is the most general sliding-window template; simpler problems (LC 567, LC 3) are special cases.
1 example
Worked Examples
have/required counter - Python
"ADOBECODEBANC" with t="ABC" → minimum window "BANC".
Expand right to satisfy all needs; shrink left while all needs still met.
from collections import Counter
def minWindow(s: str, t: str) -> str:
need = Counter(t)
window = {}
have, required = 0, len(need)
l, res, res_len = 0, [-1, -1], float('inf')
for r, c in enumerate(s):
window[c] = window.get(c, 0) + 1
if c in need and window[c] == need[c]:
have += 1
while have == required:
if (r - l + 1) < res_len:
res_len = r - l + 1
res = [l, r]
lc = s[l]
window[lc] -= 1
if lc in need and window[lc] < need[lc]:
have -= 1
l += 1
return s[res[0]:res[1]+1] if res_len != float('inf') else ""
# "ADOBECODEBANC","ABC" → "BANC"Output: "BANC"
Most complex sliding-window template; solving this cleanly demonstrates mastery of the expand/shrink pattern and have/required bookkeeping.