March 24
Minimum Window Substring
How to turn "does it contain everything?" into a satisfaction condition and shrink the window only while it stays valid.
Sliding Window Advanced 30 min TypeScript
Given two strings s and t, return the minimum substring of s that contains all the characters of t, including duplicates.
If no valid substring exists, return "".
In the SeniorPath playground, when multiple valid answers have the same length, return the one that appears first.
Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
What to notice before coding
- The problem asks for a substring, so the answer must be contiguous.
- It is not enough to contain the characters. The window must also respect the frequencies required by `t`.
- The hard part is not expanding. It is knowing when the window already satisfies everything and how far it can shrink.
Common mistakes
- treating the window as valid just because it contains the character kinds, while ignoring frequency
- continuing to expand even after the window already satisfies everything and missing the chance to minimize
Step 1 - Understand what "contains everything" really means
If t = "ABC", the window must contain:
- at least one
A - at least one
B - at least one
C
If t = "AABC", the rule changes:
- two
A - one
B - one
C
So the right question is not only "does this character exist?".
The right question is:
- did the current window already reach every required frequency?
Step 2 - Write the most direct baseline
The natural baseline is:
- fix a start
- expand the end
- once the window becomes valid, update the best answer
It works.
But it restarts too much work for every start.
Step 3 - Find the satisfaction rule
Build a need map from the frequencies in t.
Then, while expanding the window, keep a window map.
The window only becomes valid when, for every required character, window[char] >= need[char].
A good way to track that is counting how many character kinds already reached the required frequency.
Step 4 - Expand until satisfied and shrink until violated
This is the heart of the problem:
rightexpands the window- once it satisfies everything,
leftcontracts it - while it stays valid, keep shrinking
The best window is born during that contraction phase.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function minWindow(s: string, t: string): string {
// your solution here
return ""
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(charset)
Solution 1 - Test every start and expand until valid
Good baseline because it makes the validity rule visible.
function coversAll(window: Map<string, number>, need: Map<string, number>): boolean {
for (const [char, amount] of need.entries()) {
if ((window.get(char) ?? 0) < amount) {
return false
}
}
return true
}
export function minWindow(s: string, t: string): string {
const need = new Map<string, number>()
for (const char of t) {
need.set(char, (need.get(char) ?? 0) + 1)
}
let best = ""
for (let start = 0; start < s.length; start += 1) {
const window = new Map<string, number>()
for (let end = start; end < s.length; end += 1) {
const char = s[end]
window.set(char, (window.get(char) ?? 0) + 1)
if (coversAll(window, need)) {
const candidate = s.slice(start, end + 1)
if (best === "" || candidate.length < best.length) {
best = candidate
}
break
}
}
}
return best
}It works, but it repeats too much counting for every new start.
Solution 2 - Sliding window with Hash Maps and satisfaction in O(n)
Now the window moves incrementally.
export function minWindow(s: string, t: string): string {
if (t.length === 0 || s.length < t.length) {
return ""
}
const need = new Map<string, number>()
for (const char of t) {
need.set(char, (need.get(char) ?? 0) + 1)
}
const window = new Map<string, number>()
const requiredKinds = need.size
let satisfiedKinds = 0
let left = 0
let bestStart = -1
let bestLength = Infinity
for (let right = 0; right < s.length; right += 1) {
const rightChar = s[right]
window.set(rightChar, (window.get(rightChar) ?? 0) + 1)
if (need.has(rightChar) && window.get(rightChar) === need.get(rightChar)) {
satisfiedKinds += 1
}
while (satisfiedKinds === requiredKinds) {
const currentLength = right - left + 1
if (currentLength < bestLength || (currentLength === bestLength && left < bestStart)) {
bestStart = left
bestLength = currentLength
}
const leftChar = s[left]
window.set(leftChar, window.get(leftChar)! - 1)
if (need.has(leftChar) && window.get(leftChar)! < need.get(leftChar)!) {
satisfiedKinds -= 1
}
left += 1
}
}
if (bestStart === -1) {
return ""
}
return s.slice(bestStart, bestStart + bestLength)
}The strong insight here is splitting one window into two phases:
- expand until satisfied
- shrink until almost broken
What to say in the interview
A strong short explanation would be:
The problem is not only about containing the characters from
t, but also the required frequencies. The baseline tests every start and expands until it finds a valid window. The stronger version usessliding windowwith twoHash Mapsand a counter for how many character kinds already met the required frequency. Once the window satisfies everything, I shrink from the left to minimize it.
That shows that you:
- understood the real validity condition
- explained why contraction exists
- treated
sliding windowas an invariant, not a template
When this pattern shows up again
This pattern comes back when you need to:
- maintain a window with frequency counts
- distinguish “character kind present” from “enough frequency present”
- expand until satisfied and shrink until violated
The point is not memorizing
Minimum Window Substring.
The point is learning how to model window satisfaction.