Minimum Window Substring

Lesson 26/45

Loading Lesson...

Data Structures and Algorithms Arrays

Minimum Window Substring

Lesson 26/45

Minimum Window Substring

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.

Time

O(N + M)

Space

O(1) (Character set size)

Key Principle 1

Two pointer / Sliding window approach

Key Principle 2

Frequency maps for target and current window

Key Principle 3

Expand window until required counts met

Key Principle 4

Shrink from left to find minimal range

MIN_WINDOW_LAB
Current Step
Find min window in 'ADOBECODEBANC' containing all chars of 'ABC'.
Match Status
0 / 3
Playback
Character Freqs ⠿
CHARWIN / REQ
A0 / 1
B0 / 1
C0 / 1
Sliding Logic ⠿
1Map<Char, Int> targetMap = getFreq(t);
2int L = 0, R = 0, found = 0;
3while (R < s.length()) {
4    add char at R to windowCounts;
5    if (counts match) found++;
6    while (found == targetMap.size()) {
7        update best range if current is smaller;
8        remove char at L, L++;
9    }
10    R++;
11}
A
L
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Best Substring Found
???

Loading Lab...

DATA STRUCTURES • ALGORITHMS

Minimum Window Substring

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.

Time

O(N + M)

Space

O(1) (Character set size)

Key Principle 1

Two pointer / Sliding window approach

Key Principle 2

Frequency maps for target and current window

Key Principle 3

Expand window until required counts met

Key Principle 4

Shrink from left to find minimal range

MIN_WINDOW_LAB
Current Step
Find min window in 'ADOBECODEBANC' containing all chars of 'ABC'.
Match Status
0 / 3
Playback
Character Freqs ⠿
CHARWIN / REQ
A0 / 1
B0 / 1
C0 / 1
Sliding Logic ⠿
1Map<Char, Int> targetMap = getFreq(t);
2int L = 0, R = 0, found = 0;
3while (R < s.length()) {
4    add char at R to windowCounts;
5    if (counts match) found++;
6    while (found == targetMap.size()) {
7        update best range if current is smaller;
8        remove char at L, L++;
9    }
10    R++;
11}
A
L
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Best Substring Found
???