Minimum Window Substring in DSA Python - Execution Trace

Concept Flow - Minimum Window Substring

Initialize frequency map of target chars

↓

Start sliding window

↓

Expand right pointer to include chars

↓

Check if window contains all target chars

↓

Expand right

↓

Update minimum window

↓

Move left pointer

↓

Repeat until right reaches end

↓

Return min window

We use two pointers to create a sliding window that expands and shrinks to find the smallest substring containing all target characters.

Execution Sample

DSA Python

def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = end = 0
    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1

This code initializes the frequency map of target chars and starts expanding the right pointer to find a valid window.

Execution Table

Step	Operation	Window [left:right]	Chars Needed	Action	Minimum Window Found
1	Initialize	[]	{A:1, B:1, C:1}	Set need map and missing count	None
2	Expand right to 'A'	[A]	{A:0, B:1, C:1}	Found needed 'A', missing=2	None
3	Expand right to 'D'	[A,D]	{A:0, B:1, C:1}	Char 'D' not needed	None
4	Expand right to 'O'	[A,D,O]	{A:0, B:1, C:1}	Char 'O' not needed	None
5	Expand right to 'B'	[A,D,O,B]	{A:0, B:0, C:1}	Found needed 'B', missing=1	None
6	Expand right to 'E'	[A,D,O,B,E]	{A:0, B:0, C:1}	Char 'E' not needed	None
7	Expand right to 'C'	[A,D,O,B,E,C]	{A:0, B:0, C:0}	Found needed 'C', missing=0	Window [0:6] = 'ADOBEC'
8	Shrink left from 'A'	[D,O,B,E,C]	{A:1, B:0, C:0}	Lost 'A', missing=1	Window remains 'ADOBEC'
9	Expand right to 'O'	[D,O,B,E,C,O]	{A:1, B:0, C:0}	Char 'O' not needed	Window remains 'ADOBEC'
10	Expand right to 'D'	[D,O,B,E,C,O,D]	{A:1, B:0, C:0}	Char 'D' not needed	Window remains 'ADOBEC'
11	Expand right to 'E'	[D,O,B,E,C,O,D,E]	{A:1, B:0, C:0}	Char 'E' not needed	Window remains 'ADOBEC'
12	Expand right to 'B'	[D,O,B,E,C,O,D,E,B]	{A:1, B:-1, C:0}	Extra 'B', missing=1	Window remains 'ADOBEC'
13	Expand right to 'A'	[D,O,B,E,C,O,D,E,B,A]	{A:0, B:-1, C:0}	Found needed 'A', missing=0	Window [3:11] = 'EBANC'
14	Shrink left from 'D'	[O,B,E,C,O,D,E,B,A]	{A:0, B:-1, C:0}	Char 'D' not needed	Window [3:11] = 'EBANC'
15	Shrink left from 'O'	[B,E,C,O,D,E,B,A]	{A:0, B:-1, C:0}	Char 'O' not needed	Window [3:11] = 'EBANC'
16	Shrink left from 'B'	[E,C,O,D,E,B,A]	{A:0, B:0, C:0}	Lost extra 'B', missing=0	Window [6:11] = 'BANC'
17	Shrink left from 'E'	[C,O,D,E,B,A]	{A:0, B:0, C:-1}	Lost 'C', missing=1	Window remains 'BANC'
18	End of string reached	[C,O,D,E,B,A]	{A:0, B:0, C:-1}	Stop	Minimum window is 'BANC'

💡 Right pointer reached end of string; minimum window found.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 8	After Step 13	After Step 16	Final
left	0	0	0	0	1	3	6	6
right	-1	0	3	5	5	10	10	10
missing	3	2	1	0	1	0	0	0
need[A]	1	0	0	0	1	0	0	0
need[B]	1	1	0	0	0	0	0	0
need[C]	1	1	1	0	0	0	-1	-1
min_window	None	None	None	'ADOBEC'	'ADOBEC'	'EBANC'	'BANC'	'BANC'

Key Moments - 3 Insights

Why do we decrease 'missing' only when need[char] > 0?

Because 'missing' counts only needed characters. If need[char] <= 0, it means we have extra occurrences, so 'missing' should not decrease. See steps 12 and 16 in execution_table.

Why do we shrink the window from the left only when missing == 0?

Shrinking is done only when the window contains all needed chars (missing == 0) to try to find a smaller valid window. See steps 7 to 8 and 13 to 16.

What happens when we lose a needed character while shrinking?

When shrinking removes a needed char, missing increases, making the window invalid. We then stop shrinking and continue expanding. See step 8 where missing goes from 0 to 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the minimum window found?

A 'ADOBEC'

B 'BANC'

C 'EBANC'

D None

💡 Hint

Check the 'Minimum Window Found' column at step 7 in execution_table.

At which step does the 'missing' variable first become zero?

A Step 13

B Step 5

C Step 7

D Step 16

💡 Hint

Look at the 'missing' column in variable_tracker and execution_table rows.

If we remove the shrinking step, how would the minimum window change?

A It would be the entire string

B It would remain the first valid window found

C It would become empty

D It would be the last character only

💡 Hint

Shrinking tries to reduce window size; without it, minimum window stays as first valid window (see steps 7 and 8).

Concept Snapshot

Minimum Window Substring:
- Use two pointers (left, right) to create a sliding window.
- Expand right to include chars until all needed chars are in window.
- Shrink left to minimize window while keeping all chars.
- Track counts with a frequency map and missing count.
- Return smallest window containing all target chars.

Full Transcript

The Minimum Window Substring problem finds the smallest substring in a string that contains all characters of a target string. We use a sliding window approach with two pointers: left and right. We keep a frequency map of needed characters and a count of how many are missing. We expand the right pointer to include characters, decreasing missing when a needed char is found. When missing reaches zero, the window contains all needed chars. Then we try to shrink the window from the left to find a smaller valid window. If shrinking removes a needed char, missing increases and we stop shrinking. We repeat until the right pointer reaches the end. The smallest window found during this process is returned.