Minimum Window Substring in DSA Python

Mental Model

Find the smallest part of a big string that contains all characters of a smaller string. We slide a window over the big string and adjust it to keep all needed characters while trying to make it as small as possible.

Analogy: Imagine you have a long shelf of books (big string) and a list of books you want to borrow (small string). You slide a box along the shelf to pick up all the books on your list. You try to make the box as small as possible while still holding all the books you need.

big string:  A B C D E F G H I J K L M N O P
window:       ↑           ↑
              start       end
window covers substring from start to end pointers

Dry Run Walkthrough

Input: big string: "ADOBECODEBANC", small string: "ABC"

Goal: Find the smallest substring in the big string that contains all characters A, B, and C.

Step 1: Expand end pointer to include characters until all A, B, C are in the window

A [D O B E C] O D E B A N C
start=0, end=5, window="ADOBEC"

Why: We need to include all required characters before trying to shrink the window

Step 2: Shrink start pointer to remove unnecessary characters while keeping all required

[D O B E C] O D E B A N C
start=1, end=5, window="DOBEC"

Why: Remove 'A' at start to see if window still contains all required chars

Step 3: Shrink start pointer further to remove 'D' which is not needed

[O B E C] O D E B A N C
start=2, end=5, window="OBEC"

Why: Try to make window smaller while still containing all required chars

Step 4: Shrink start pointer further to remove 'O' which is not needed

[B E C] O D E B A N C
start=3, end=5, window="BEC"

Why: Window still contains all required chars, so we can shrink more

Step 5: Try to shrink start pointer more but removing 'B' loses a required char, so stop shrinking

[B E C] O D E B A N C
start=3, end=5, window="BEC"

Why: Cannot remove 'B' as it is required, so window is minimal here

Step 6: Expand end pointer to include next characters to find smaller window

B E C O [D E B A] N C
start=3, end=9, window="BECODEBA"

Why: Try to find another window that might be smaller

Step 7: Shrink start pointer to remove 'B' and 'E' until window still contains all required chars

[B A N C] N C
start=9, end=12, window="BANC"

Why: Found smaller window containing all required chars

Step 8: Shrink start pointer to remove 'B' and 'E' until window still contains all required chars

[B A N C]
start=9, end=12, window="BANC"

Why: Window is minimal and contains all required chars

Result:

B A N C
start=9, end=12, smallest window containing A, B, C is "BANC"

Annotated Code

DSA Python

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""

        dict_t = Counter(t)  # count chars needed
        required = len(dict_t)  # unique chars needed

        l, r = 0, 0  # window pointers
        formed = 0  # how many unique chars in current window match required count
        window_counts = {}

        ans = float('inf'), None, None  # window length, left, right

        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  # one required char count matched

            while l <= r and formed == required:
                character = s[l]

                # update answer if smaller window found
                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  # lost a required char count

                l += 1  # shrink window from left

            r += 1  # expand window from right

        return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

# Driver code
s = "ADOBECODEBANC"
t = "ABC"
sol = Solution()
print(sol.minWindow(s, t))

dict_t = Counter(t) # count chars needed

count how many of each character we need

required = len(dict_t) # unique chars needed

number of unique characters to match

while r < len(s):

expand window by moving right pointer

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

add current character to window count

if character in dict_t and window_counts[character] == dict_t[character]: formed += 1

increment formed when a required char count is met

while l <= r and formed == required:

try to shrink window from left while all required chars are present

if r - l + 1 < ans[0]: ans = (r - l + 1, l, r)

update smallest window found

window_counts[character] -= 1 if character in dict_t and window_counts[character] < dict_t[character]: formed -= 1

reduce count of left char and update formed if needed

l += 1

shrink window from left

r += 1

expand window from right

Output

BANC

Complexity Analysis

Time: O(n) because each character is visited at most twice by left and right pointers

Space: O(m) where m is the number of unique characters in t, for counting needed chars

vs Alternative: Naive approach checks all substrings which is O(n^2) or worse; sliding window reduces to linear time

Edge Cases

Empty big string or empty small string

Returns empty string immediately

DSA Python

if not t or not s:
    return ""

Small string has characters not in big string

No valid window found, returns empty string

DSA Python

return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

Small string is a single character

Finds first occurrence of that character in big string

DSA Python

formed == required check ensures correct window

When to Use This Pattern

When asked to find the smallest substring containing all characters of another string, use the sliding window with two pointers and character counts to efficiently find the minimum window.

Common Mistakes

Mistake: Not updating the formed count correctly when shrinking the window
Fix: Decrease formed when a required character count falls below needed after shrinking

Mistake: Not checking if the current window contains all required characters before shrinking
Fix: Only shrink window when formed equals required unique characters count

Summary

Finds the smallest substring in a big string containing all characters of a smaller string.

Use when you need to find a minimal window containing all required elements in order.

The key is to expand and shrink a window using two pointers while tracking character counts.

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