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.