📖 7 min read
Last updated on

Minimum Window Substring — Coding Interview Walkthrough

By intervu.dev

The core approach: Minimum Window Substring is solved with a sliding window and character frequency maps in O(n+m) time and O(m) space. Expand the right pointer until the window contains all required characters. Then shrink the left pointer while the window stays valid, recording the minimum valid window found. Repeat until the right pointer exhausts the string.

You’re in a coding interview. The interviewer gives you s = "ADOBECODEBANC" and t = "ABC" and asks for the minimum window in s that contains all characters of t. You write a sliding window, find a valid window, and return it. The interviewer changes the input to t = "AAB" and your solution returns a window with only one A. You used a set instead of a frequency map, and now there’s a correctness bug you need to fix with the clock running.

This walkthrough covers the full solution: the two-phase sliding window, the formed counter that keeps validity checks O(1), and the frequency map design that handles duplicate characters correctly.

Already know how to solve Minimum Window Substring? Try a Minimum Window Substring mock interview on Intervu →

The Problem

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such window exists, return "".

(LeetCode #76)

Example 1

Input s = "ADOBECODEBANC", t = "ABC"

Output "BANC"

Example 2

Input s = "a", t = "a"

Output "a"

Example 3

Input s = "a", t = "b"

Output ""

In Example 1, the shortest window containing A, B, and C is "BANC" (length 4). The key challenge: t can contain duplicate characters. t = "AA" requires the window to contain at least two As.

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Sliding window patternDo you know when to expand vs. shrink?
Frequency map designDo you use two maps (need vs. window) and a formed counter?
Duplicate character handlingDoes your solution require multiple occurrences when t has duplicates?
Window validity trackingDo you use a formed counter rather than re-scanning?
Optimization instinctDo you shrink greedily to find the minimum?

Step 1: Clarifying Questions

1. Can t contain duplicate characters? Yes, this is the critical clarification. If t = "AA", the window needs at least two As. Using a set instead of a counter for t produces wrong answers.

2. Is the answer guaranteed to exist? No. Return "" if no valid window exists.

3. Are characters case-sensitive? Yes. "A" and "a" are distinct.

4. Does the window need to be contiguous? Yes, a contiguous slice of s.

Step 2: A First (Non-Optimal) Idea

Check every possible substring:

from collections import Counter

def min_window_brute(s: str, t: str) -> str:
    need = Counter(t)
    best = ""
    for left in range(len(s)):
        for right in range(left + 1, len(s) + 1):
            window_count = Counter(s[left:right])
            if all(window_count[c] >= need[c] for c in need):
                if not best or len(s[left:right]) < len(best):
                    best = s[left:right]
    return best

O(n^2 x m) with n^2 substrings and O(m) validity checks. Far too slow for n = 100,000.

Step 3: The Key Insight

Use a two-phase sliding window. Expand the right pointer until the window is valid (contains all required characters at required frequencies). Then shrink the left pointer as far as possible while the window stays valid, recording the minimum. The formed counter tracks how many distinct characters in t are currently satisfied, making validity checks O(1).

When adding a character: if its window count now equals its required count, increment formed. When removing: if its count drops below required, decrement formed. The window is valid when formed == required.

String 'ADOBECODEBANC' with sliding window highlighting 'BANC' (indices 9-12) as the minimum window containing all characters of 'ABC'.

Step 4: Optimal Strategy

  1. Build need from t. Let required = len(need).
  2. Initialize window_counts = {}, formed = 0, left = 0.
  3. Track best = (infinity, 0, 0).
  4. Expand with right:
    • Add s[right] to window_counts.
    • If character is in need and count matches, increment formed.
    • While formed == required, try shrinking:
      • Update best if current window is smaller.
      • Remove s[left], check if formed should decrement.
      • Advance left.
  5. Return the best window or "".

Python Implementation

from collections import Counter

def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""

    need = Counter(t)
    required = len(need)

    window_counts = {}
    formed = 0

    left = 0
    best = float("inf"), 0, 0

    for right in range(len(s)):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1

        if char in need and window_counts[char] == need[char]:
            formed += 1

        while formed == required and left <= right:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)

            left_char = s[left]
            window_counts[left_char] -= 1

            if left_char in need and window_counts[left_char] < need[left_char]:
                formed -= 1

            left += 1

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

For s = "ADOBECODEBANC", t = "ABC":

  1. Expand right to index 5 (C): window = "ADOBEC", formed = 3
  2. Shrink: remove A, formed = 2. Best so far = "ADOBEC" (len 6)
  3. Expand to index 10 (A): formed = 3 again
  4. Shrink through D, O, B: formed drops when removing B. Best = "CODEBA" (len 6)
  5. Expand to index 12 (C): formed = 3
  6. Shrink through E, C, O, D, E: window = "BANC" (len 4). Best updated.

Result: "BANC" ✓

Time & Space Complexity

AspectComplexityExplanation
TimeO(n + m)Each character added and removed at most once; building need costs O(m)
SpaceO(m + k)need stores m characters; window_counts stores at most k unique chars

Common Interview Mistakes

  1. Not tracking formed, re-checking validity from scratch. Re-computing all(window_counts[c] >= need[c] for c in need) each step makes it O(n x m).

  2. Using a set instead of a counter for t. Fails on duplicates. t = "AA" requires two As.

  3. Decrementing formed too eagerly. Only decrement when count drops below required, not on every decrease.

  4. Incrementing formed for characters not in need. Track only characters in t.

  5. Off-by-one in the return slice. s[left:right + 1] because Python slicing is exclusive on the right.

  6. Using if instead of while for the shrink phase. The window must shrink as far as possible.

What a Strong Candidate Sounds Like

“I’ll use a two-phase sliding window. Expand right until the window is valid, then shrink from left as far as possible while valid, recording the minimum. To check validity in O(1), I maintain a formed counter: it increments when a character’s window count hits its required amount, decrements when it drops below. The window is valid when formed equals the number of distinct characters in t. Every character is added and removed at most once, giving O(n + m) total.”

Example Interview Dialogue

Interviewer: What happens when t has duplicate characters?

Candidate: The need map captures frequencies: t = "AAB" gives need = {'A': 2, 'B': 1}. formed only increments for 'A' when window_counts['A'] reaches exactly 2. Adding a third A doesn’t change formed. When shrinking, formed decrements only when window_counts['A'] drops below 2.

Interviewer: Could you solve this without the formed counter?

Candidate: You could check all(window_counts.get(c, 0) >= need[c] for c in need) each step, but that’s O(m) per step, making the solution O(n x m). The formed counter reduces that to O(1).

These problems build on the same sliding window and frequency tracking patterns:

Frequently Asked Questions

What is the optimal pattern for locating a Minimum Window Substring?

Extending a dynamic right pointer alongside a tracking Hash Map fulfills the optimal Sliding Window strategy. You aggressively stretch the array window forward dynamically to find missing characters, and squeeze the trailing left pointer backwards to minimize window size perfectly.

What is the time complexity of the Sliding Window substring strategy?

The dual pointers exclusively scan forwards sequentially alongside the target string sequence without redundantly backpedaling, yielding an absolute optimal O(U + T) execution timescale depending tightly on respective character limits.

Practice This in a Mock Interview

This is a problem where the complexity is in the interactions between moving parts: the two-phase window, the formed counter, the frequency map. Candidates who understand each piece individually still mix up when to increment vs. decrement formed, or forget while vs. if in the shrink phase.

The only way to make those interactions feel automatic is to implement this from scratch, out loud, under time pressure.

Start a mock interview for Minimum Window Substring on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →