Minimum Window Substring in DSA Python - Build from Scratch

Minimum Window Substring

📖 Scenario: Imagine you are working on a text analysis tool that needs to find the smallest part of a document containing all the keywords a user is searching for. This helps users quickly find the most relevant snippet without reading the entire text.

🎯 Goal: Build a program that finds the minimum window substring in a given string s that contains all the characters of another string t. The program should return the smallest substring of s that includes every character in t at least once.

📋 What You'll Learn

Create a string variable s with the value "ADOBECODEBANC".

Create a string variable t with the value "ABC".

Create a dictionary called dict_t that counts the frequency of each character in t.

Create variables required, formed, l, r, window_counts, ans to help find the minimum window substring.

Use a while loop to expand the right pointer r over s and update counts.

Use a nested while loop to contract the left pointer l when the current window contains all characters of t.

Print the minimum window substring found or an empty string if no such window exists.

💡 Why This Matters

🌍 Real World

Finding the shortest snippet in a document that contains all search keywords helps users quickly locate relevant information.

💼 Career

This technique is useful in search engines, text editors, and any software that needs efficient substring searching.

1

Create the input strings

Create a string variable called s with the value "ADOBECODEBANC" and another string variable called t with the value "ABC".

DSA Python

# Create the input strings s and t
# Your code here

Hint

Use simple assignment to create the two strings exactly as given.

2

Count characters in t

Create a dictionary called dict_t that counts how many times each character appears in the string t. Use a dictionary comprehension or a loop.

DSA Python

s = "ADOBECODEBANC"
t = "ABC"
# Create dict_t to count characters in t
# Your code here

Hint

Loop over each character in t and update the count in dict_t.

3

Initialize variables for sliding window

Create variables: required as the number of unique characters in dict_t, formed as 0, l and r as 0, window_counts as an empty dictionary, and ans as a tuple (float('inf'), None, None).

DSA Python

s = "ADOBECODEBANC"
t = "ABC"
dict_t = {}
for char in t:
    dict_t[char] = dict_t.get(char, 0) + 1
# Initialize variables required, formed, l, r, window_counts, ans
# Your code here

Hint

Set up all variables needed to track the window and counts.

4

Find and print the minimum window substring

Use a while loop to move the right pointer r over s. Update window_counts for each character. If the count matches dict_t, increase formed. Then use a nested while loop to move the left pointer l to try to minimize the window while formed == required. Update ans with the smallest window found. After the loops, print the substring of s from ans[1] to ans[2] if ans[0] is not infinity; otherwise print an empty string.

DSA Python

s = "ADOBECODEBANC"
t = "ABC"
dict_t = {}
for char in t:
    dict_t[char] = dict_t.get(char, 0) + 1

required = len(dict_t)
formed = 0
l, r = 0, 0
window_counts = {}
ans = (float('inf'), None, None)
# Use while loops to find the minimum window substring
# Your code here

Hint

Use two pointers to expand and contract the window. Update counts and track the smallest valid 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