#76 - Minimum Window Substring
HardArray / String
Given 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 "".
| Input | Output |
|---|---|
s = "ADOBECODEBANC", t = "ABC" | "BANC" |
s = "a", t = "a" | "a" |
s = "a", t = "aa" | "" |
Solution Space
ts
/**
* Finds the smallest substring of s containing all characters of t.
*
* @param s Source string to search within
* @param t Pattern string whose characters must all appear in the window
* @returns The minimum window substring, or "" if none exists
*/
export function minWindow(s: string, t: string): string {
if (t.length > s.length) return "";
// Frequency map for characters we still need
const need = new Map<string, number>();
for (const ch of t) {
need.set(ch, (need.get(ch) ?? 0) + 1);
}
// Number of unique characters in t that are fully satisfied in the window
let formed = 0;
const required = need.size;
// Window character counts
const windowCounts = new Map<string, number>();
let left = 0;
let minLen = Infinity;
let minStart = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
windowCounts.set(ch, (windowCounts.get(ch) ?? 0) + 1);
// A required character just reached its needed frequency
if (need.has(ch) && windowCounts.get(ch) === need.get(ch)) {
formed++;
}
// Contract the window from the left while it's still valid
while (formed === required) {
const windowSize = right - left + 1;
if (windowSize < minLen) {
minLen = windowSize;
minStart = left;
}
const leftCh = s[left];
windowCounts.set(leftCh, windowCounts.get(leftCh)! - 1);
// Dropping below the required count breaks the constraint
if (need.has(leftCh) && windowCounts.get(leftCh)! < need.get(leftCh)!) {
formed--;
}
left++;
}
}
return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
Approach: sliding window with two frequency maps and a "formed" counter – expand the right pointer to include characters, and shrink the left pointer when the window contains all required characters.
Time: O(|s| + |t|) – each pointer traverses `s` at most once, plus O(|t|) to build the need map.
Space: O(|s| + |t|) – worst-case both maps store every unique character.
Alternative approaches:
| Approach | Idea | Time | Space |
|---|---|---|---|
| Filtered index list | Pre-filter indices of s that appear in t, then slide over this shorter list. | O(|s| + |t|) but faster in practice when |s| ≫ |t| | O(|s| + |t|) |
| Brute force | Check all substrings of s, verify each contains all of t. | O(|s|² · |t|) | O(|t|) |
Why the sliding-window approach is preferred:
- Achieves optimal O(|s| + |t|) time with straightforward logic.
- The
formedcounter avoids scanning the entire frequency map on every step, keeping the inner loop O(1) amortised.