Minimum Window Substring in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the left pointer for the sliding window.

DSA Python

left = [1]

Drag options to blanks, or click blank then click option'

A1

B0

C-1

Dlen(s)

Attempts:

3 left

💡 Hint

Common Mistakes

Starting left pointer at 1 skips the first character.

Using -1 causes index errors.

Setting left to length of string is out of bounds.

The left pointer starts at index 0 to begin the sliding window from the start of the string.

2fill in blank

medium

Complete the code to update the count of characters in the current window.

DSA Python

window_counts[character] = window_counts.get(character, 0) [1] 1

Drag options to blanks, or click blank then click option'

A+

B-

C*

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction decreases the count incorrectly.

Multiplication or floor division are not suitable for counting.

We add 1 to the count of the current character to track its frequency in the window.

3fill in blank

hard

Fix the error in the condition to check if the current window contains all required characters.

DSA Python

if formed [1] required:

Drag options to blanks, or click blank then click option'

A>

B!=

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' causes the condition to fail when window is valid.

Using '<' or '>' does not correctly check completeness.

The window is valid only when the number of formed characters equals the required number.

4fill in blank

hard

Fill both blanks to correctly update the minimum window size and substring.

DSA Python

if right - left + 1 < [1]:
    min_len = right - left + 1
    min_substr = s[[2]:right + 1]

Drag options to blanks, or click blank then click option'

Amin_len

Bleft

Cright

Dmax_len

Attempts:

3 left

💡 Hint

Common Mistakes

Using max_len instead of min_len causes wrong comparisons.

Using right as start index slices wrong substring.

We compare the current window size with the minimum length found so far and update if smaller. The substring is sliced from left to right+1.

5fill in blank

hard

Fill all three blanks to correctly shrink the window and update counts.

DSA Python

character = s[[1]]
window_counts[character] -= 1
if window_counts[character] < dict_t.get(character, 0):
    formed -= [2]
left += [3]

Drag options to blanks, or click blank then click option'

Aleft

B1

Cright

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using right instead of left causes wrong character removal.

Increasing left by 0 does not shrink the window.

We get the character at the left pointer, decrease its count, check if formed decreases, and then move left pointer by 1 to shrink the window.

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