Arrays & Strings/Practice/Minimum Window Substring

Minimum Window Substring - Step-by-Step Solution

hardTime: O(|s| + |t|)Space: O(|s| + |t|)

Grow a window with a right pointer until it contains every character of t (tracked with two frequency counts and a "satisfied" counter). Then pull the left edge in as far as it will go, recording the smallest valid window you ever see.

Why it works

Both pointers only ever move forward, and each moves at most |s| times - so even though the window stretches and shrinks, the total work is O(|s| + |t|), not O(|s| × |t|). The frequency counts let you test "does this window cover t?" in constant time.

The problem

Given strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included. Return empty string if no such window exists.

Hints

  • Use two pointers (left, right) to expand and contract the window.
  • Keep a frequency count of required characters vs. characters currently in window.
  • Track how many unique characters from t are satisfied in the current window.
  • Shrink from the left once all characters are satisfied to minimize window.

Test cases

InputExpected
min_window("ADOBECODEBANC", "ABC")"BANC"
min_window("a", "a")"a"
min_window("a", "aa")""

Reference starter code

from collections import Counter

def min_window(s, t):
    # Sliding window with character frequency tracking
    pass

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window("a", "a"))                # "a"
print(min_window("a", "aa"))               # ""

More challenges in this topic

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.

Studying Arrays & Strings but not ready to grind? Get the 30-day plan by email.
One email with the study plan. No spam, unsubscribe anytime.