DSA With AI
Week 2 ยท Sliding Window

Minimum Window Substring

Return the smallest substring of s that contains every character from t with required multiplicities.

Hard Sliding Window Week 2 Practice runner

Frame the problem

  • Multiplicity matters.
  • Return an empty string if no window exists.
  • The window must be contiguous.
1. Reveal example inputs and outputs

Example 1

Input:

min_window("ADOBECODEBANC", "ABC")

Output:

"BANC"

Example 2

Input:

min_window("a", "a")

Output:

"a"
2. Brute force first

How would you check every substring against t's counts? Which counts can be updated as the window moves?

3. Reveal the insight ladder
  1. Count the required characters from t.
  2. Expand right until all required character counts are satisfied.
  3. Then shrink left while preserving validity.
  4. Record the smallest valid window seen.
4. Dry run before code
  1. s = ADOBECODEBANC, t = ABC.
  2. The first valid window is ADOBEC.
  3. Shrinking and expanding eventually reaches BANC.
  4. BANC is the shortest valid window.
5. Reveal final Python solution 
from collections import Counter, defaultdict

def min_window(s, t):
    need = Counter(t)
    window = defaultdict(int)
    have = 0
    required = len(need)
    best = (float("inf"), 0, 0)
    left = 0

    for right, char in enumerate(s):
        window[char] += 1
        if char in need and window[char] == need[char]:
            have += 1

        while have == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            left_char = s[left]
            window[left_char] -= 1
            if left_char in need and window[left_char] < need[left_char]:
                have -= 1
            left += 1

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

Complexity: Time O(|s| + |t|), space O(distinct characters in s and t).

Interview narration

  • I maintain a valid window count, not just a set of seen characters.
  • The have counter says how many required character types are fully satisfied.
  • Once valid, I shrink aggressively to find the minimum.

Common traps

  • Ignoring duplicate requirements in t.
  • Shrinking before the window is valid.
  • Returning the first valid window rather than the smallest.

Follow-up drills

1. Why track have by character type instead of total characters?

It lets us know exactly when every required count threshold is met, including duplicates, without scanning the whole need map each time.

2. What if t is empty?

Clarify with the interviewer. Most platforms avoid this case; a reasonable return is an empty string.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.