Minimum Window Substring
HardSmallest window covering all needed characters
Stretch a window until it holds every letter you need, then squeeze it as small as possible.
The idea
Expand the right edge until the window contains every required character, then contract the left edge as far as possible while it stays valid. Record the smallest valid window.
A
D
O
B
E
C
O
D
E
B
A
N
C
0
1
2
3
4
5
6
7
8
9
10
11
12
Step 1 of 12. Brute force: from each start, grow until the window covers "ABC", keep the shortest. Values: A, D, O, B, E, C, O, D, E, B, A, N, C.
1/12
Brute force
timeO(n²·m)spaceO(m)
Every window.
1for (let i = 0; i < n; i++)2 for (let j = i; j < n; j++)3 if (covers(s.slice(i, j + 1), t))4 best = shorter(best, s.slice(i, j + 1));Input
- array
- [A, D, O, B, E, C, O, D, E, B, A, N, …]
Output
- shortest
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "ADOBECODEBANC", t = "ABC"
- Output:
- "BANC"
- Explanation:
- "BANC" is the shortest window with A, B and C.
Example 2
- Input:
- s = "a", t = "a"
- Output:
- "a"
- Explanation:
- The whole string is the window.
Example 3
- Input:
- s = "a", t = "aa"
- Output:
- ""
- Explanation:
- Not enough a's → empty string.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.