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.

Practice

1. What is the main goal of the Minimum Window Substring problem?

easy

A. Find the smallest substring in a string that contains all characters of another string

B. Find the longest substring without repeating characters

C. Count the number of substrings that contain a specific character

D. Sort characters of a string in ascending order

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the smallest part of a string that has all characters from another string.

2. Step 2: Compare options with problem goal

   Only Find the smallest substring in a string that contains all characters of another string matches the goal of finding the smallest substring containing all characters of another string.

3. Final Answer:

   Find the smallest substring in a string that contains all characters of another string -> Option A

4. Quick Check:

   Minimum Window Substring = Find smallest substring with all chars [OK]

Hint: Look for smallest substring containing all target chars [OK]

Common Mistakes:

• Confusing with longest substring problems
• Thinking about sorting instead of substring search
• Ignoring the requirement to include all characters

2. Which of the following Python code snippets correctly initializes a dictionary to count characters in string t for the Minimum Window Substring problem?

easy

A. count = dict.fromkeys(t, 0)

B. count = {0: char for char in t}

C. count = {char: 1 for char in t}

D. count = {char: t.count(char) for char in t}

Solution

1. Step 1: Understand dictionary initialization for counting

   We want a dictionary with keys as characters from t and values initialized to the count of each character in t.

2. Step 2: Check each option

   count = {char: t.count(char) for char in t} correctly counts the occurrences of each character in t.

3. Final Answer:

   count = {char: t.count(char) for char in t} -> Option D

4. Quick Check:

   Use dict comprehension with t.count(char) to initialize counts [OK]

Hint: Use dict comprehension with t.count(char) to initialize counts [OK]

Common Mistakes:

• Setting counts to 0 instead of actual counts
• Swapping keys and values in dict comprehension
• Using invalid dictionary syntax

3. What will be the output of the following Python code snippet?

def min_window(s, t):
    from collections import Counter
    dict_t = Counter(t)
    required = len(dict_t)
    l, r = 0, 0
    formed = 0
    window_counts = {}
    ans = float('inf'), None, None
    while r < len(s):
        character = s[r]
        window_counts[character] = window_counts.get(character, 0) + 1
        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1
        while l <= r and formed == required:
            character = s[l]
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)
            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1
            l += 1
        r += 1
    return '' if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

print(min_window('ADOBECODEBANC', 'ABC'))

medium

A. NONE

B. ADOBEC

C. BANC

D. CODEBA

Solution

1. Step 1: Understand the sliding window logic

   The code finds the smallest substring in 'ADOBECODEBANC' containing all chars 'A', 'B', 'C'.

2. Step 2: Trace the window updates

   The smallest such substring is 'BANC' starting at index 9 and ending at 12.

3. Final Answer:

   BANC -> Option C

4. Quick Check:

   Minimum window substring = BANC [OK]

Hint: Trace window expansion and contraction carefully [OK]

Common Mistakes:

• Confusing substring boundaries
• Not updating formed count correctly
• Returning empty string incorrectly

4. Identify the bug in the following code snippet for Minimum Window Substring and select the correct fix:

def min_window(s, t):
    from collections import Counter
    dict_t = Counter(t)
    required = len(dict_t)
    l, r = 0, 0
    formed = 0
    window_counts = {}
    ans = float('inf'), None, None
    while r < len(s):
        character = s[r]
        window_counts[character] = window_counts.get(character, 0) + 1
        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1
        while l <= r and formed == required:
            character = s[l]
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)
            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1
            l += 1
        r += 1
    return s[ans[1]:ans[2]+1]

medium

A. Initialize window_counts with dict_t keys

B. Return empty string if no valid window found

C. Use a list instead of dict for window_counts

D. Remove formed variable

Solution

1. Step 1: Analyze return statement

   The code returns substring using ans indices without checking if a valid window was found.

2. Step 2: Fix missing empty string return

   If no window found, ans[0] remains infinity, so return empty string to avoid error.

3. Final Answer:

   Return empty string if no valid window found -> Option B

4. Quick Check:

   Check ans[0] before return to avoid errors [OK]

Hint: Always check if a valid window was found before returning [OK]

Common Mistakes:

• Returning substring without validation
• Ignoring empty result cases
• Overcomplicating window_counts initialization

5. Given strings s = 'aabbcc' and t = 'abc', which of the following modifications to the Minimum Window Substring algorithm will correctly find the smallest substring containing all characters of t even if t has duplicate characters like 'aabc'?

hard

A. Use a frequency counter for t and compare counts exactly in the window

B. Only check if characters exist in the window, ignoring counts

C. Sort s and t and find common prefix

D. Use a set for t instead of a counter

Solution

1. Step 1: Understand the need for frequency counts

   When t has duplicates, we must count how many times each character appears and match exactly.

2. Step 2: Choose the correct approach

   Using a frequency counter for t and comparing counts in the window ensures all duplicates are included.

3. Final Answer:

   Use a frequency counter for t and compare counts exactly in the window -> Option A

4. Quick Check:

   Count duplicates exactly using frequency counters [OK]

Hint: Count character frequencies to handle duplicates correctly [OK]

Common Mistakes:

• Ignoring duplicate characters in t
• Using sets which lose count information
• Sorting strings which doesn't help substring search