Minimum Window Substring

hard

Find the smallest substring that contains all characters of another string

Minimum Window Substring

Key Insight

Expand right until all target characters covered, then shrink left to minimize

Step 1Target Characters
Need: A:1, B:1, C:1
A
0
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12

Identify which characters we need to cover from string t.

1 / 6
Practice the Code

Step-by-Step Walkthrough: Minimum Window Substring

Expand right until all target characters covered, then shrink left to minimize

  1. Target Characters

    Identify which characters we need to cover from string t.

  2. Expand to Cover

    Expand right until all target characters are in the window.

  3. Shrink Left

    Try to shrink from left. Removing A loses coverage.

  4. Expand More

    Expand right to find another A and restore coverage.

  5. Shrink to Minimum

    Shrink left aggressively. Window BANC covers all characters.

  6. Minimum Window

    BANC is the shortest substring containing A, B, and C.