Minimum Window Substring in DSA C - Execution Trace

Concept Flow - Minimum Window Substring

Start

↓

Initialize frequency map of target chars

↓

Set two pointers: left=0, right=0

↓

Expand right pointer to include chars

↓

Update window counts and check if window valid

↓

While window valid: try to shrink from left

↓

Update minimum window if smaller

↓

Move left pointer to shrink window

↓

Repeat expand/shrink until right reaches end

↓

Return minimum window substring or empty if none

We move two pointers over the string to find the smallest substring containing all target chars, expanding right to include chars and shrinking left to minimize.

Execution Sample

DSA C

s = "ADOBECODEBANC";
t = "ABC";
// Find min window in s containing all chars of t

Find the smallest substring in s that contains all characters from t.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Window Counts	Valid Count	Minimum Window	Visual State
1	Initialize frequency map for t	0	0	{"A":0,"B":0,"C":0}	0	null	""
2	Expand right to 'A'	0	0	{"A":1,"B":0,"C":0}	1	null	[A]
3	Expand right to 'D'	0	1	{"A":1,"B":0,"C":0}	1	null	[A D]
4	Expand right to 'O'	0	2	{"A":1,"B":0,"C":0}	1	null	[A D O]
5	Expand right to 'B'	0	3	{"A":1,"B":1,"C":0}	2	null	[A D O B]
6	Expand right to 'E'	0	4	{"A":1,"B":1,"C":0}	2	null	[A D O B E]
7	Expand right to 'C'	0	5	{"A":1,"B":1,"C":1}	3	Window 'ADOBEC'	[A D O B E C]
8	Shrink left from 'A'	1	5	{"A":0,"B":1,"C":1}	2	Window 'ADOBEC'	[D O B E C]
9	Expand right to 'O'	1	6	{"A":0,"B":1,"C":1}	2	Window 'ADOBEC'	[D O B E C O]
10	Expand right to 'D'	1	7	{"A":0,"B":1,"C":1}	2	Window 'ADOBEC'	[D O B E C O D]
11	Expand right to 'E'	1	8	{"A":0,"B":1,"C":1}	2	Window 'ADOBEC'	[D O B E C O D E]
12	Expand right to 'B'	1	9	{"A":0,"B":2,"C":1}	2	Window 'ADOBEC'	[D O B E C O D E B]
13	Expand right to 'A'	1	10	{"A":1,"B":2,"C":1}	3	Window 'ADOBEC'	[D O B E C O D E B A]
14	Shrink left from 'D'	2	10	{"A":1,"B":2,"C":1}	3	Window 'DOBECODEBA'	[O B E C O D E B A]
15	Shrink left from 'O'	3	10	{"A":1,"B":2,"C":1}	3	Window 'OBECODEBA'	[B E C O D E B A]
16	Shrink left from 'B'	4	10	{"A":1,"B":1,"C":1}	3	Window 'BECODEBA'	[E C O D E B A]
17	Shrink left from 'E'	5	10	{"A":1,"B":1,"C":1}	3	Window 'ECODEBA'	[C O D E B A]
18	Shrink left from 'C'	6	10	{"A":1,"B":1,"C":0}	2	Window 'ECODEBA'	[O D E B A]
19	Expand right to 'N'	6	11	{"A":1,"B":1,"C":0}	2	Window 'ECODEBA'	[O D E B A N]
20	Expand right to 'C'	6	12	{"A":1,"B":1,"C":1}	3	Window 'ECODEBANC'	[O D E B A N C]
21	Shrink left from 'O'	7	12	{"A":1,"B":1,"C":1}	3	Window 'CODEBANC'	[D E B A N C]
22	Shrink left from 'D'	8	12	{"A":1,"B":1,"C":1}	3	Window 'ODEBANC'	[E B A N C]
23	Shrink left from 'E'	9	12	{"A":1,"B":0,"C":1}	2	Window 'ODEBANC'	[B A N C]
24	End: right reached end, no smaller valid window	9	12	{"A":1,"B":0,"C":1}	2	Window 'BANC'	[B A N C]

💡 Right pointer reached end of string; minimum window found is 'BANC'

Variable Tracker

Variable	Start	After Step 7	After Step 13	After Step 20	Final
left	0	0	1	6	9
right	0	5	10	12	12
window_counts	{}	{"A":1,"B":1,"C":1}	{"A":1,"B":2,"C":1}	{"A":1,"B":1,"C":1}	{"A":1,"B":0,"C":1}
valid_count	0	3	3	3	2
min_window	null	"ADOBEC"	"ADOBEC"	"ECODEBANC"	"BANC"

Key Moments - 3 Insights

Why do we shrink the window from the left only when the window is valid?

Because shrinking the window when it is not valid would lose required characters. See steps 7 to 8 where shrinking starts only after valid_count reaches 3.

Why do we keep track of valid_count instead of just checking window_counts every time?

valid_count tracks how many required characters meet their needed frequency, making it efficient to know when the window is valid without checking all counts each time. See column 'Valid Count' in execution_table.

Why does the window_counts for 'B' increase beyond the needed count?

Because the window can have extra occurrences of characters. We only care if counts meet or exceed required counts. See step 13 where 'B' count is 2 but valid_count remains 3.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the minimum window substring found?

A "ADOBEC"

B "DOBEC"

C "BANC"

D "CODEBA"

💡 Hint

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

At which step does the valid_count first reach 3?

A Step 5

B Step 7

C Step 13

D Step 20

💡 Hint

Look at the 'Valid Count' column in execution_table to find when it first becomes 3.

If we did not shrink the window from the left, what would happen to the minimum window substring?

A It would remain the same

B It would become larger or not minimal

C It would become empty

D It would contain fewer characters

💡 Hint

Refer to steps 7 to 17 where shrinking left reduces window size and updates minimum window.

Concept Snapshot

Minimum Window Substring:
- Use two pointers (left, right) to slide over string
- Expand right to include chars until window valid
- Shrink left to minimize window while valid
- Track counts of chars and valid matches
- Return smallest valid window or empty if none

Full Transcript

Minimum Window Substring finds the smallest substring in a string that contains all characters of another string. We use two pointers, left and right, to create a sliding window. We expand the right pointer to include characters and update counts. When the window contains all required characters, we try to shrink it from the left to find the smallest valid window. We track counts of characters and how many required characters are fully matched. The process continues until the right pointer reaches the end. The smallest valid window found is returned, or empty if none exists.