How to Explain Minimum Window Substring in a Coding Interview (Step-by-Step)

Minimum Window Substring is the hardest sliding window problem you’ll encounter. The window mechanics aren’t new — expand right, shrink left — but the formed and required counters are the trick that makes it efficient. Nail those two variables and the rest follows naturally.

In this post, you’ll learn exactly how to walk an interviewer through this problem: the two-counter trick, the expand-then-shrink loop, a full step-by-step trace, and the edge cases interviewers always probe.

Problem Statement

Examples

Constraints

• m == s.length, n == t.length
• 1 <= m, n <= 10⁵
• s and t consist of uppercase and lowercase English letters

What Is the Problem?

“I need to find the smallest contiguous substring of s that contains every character from t — including duplicates. If t has two A’s, the window must contain at least two A’s. If no such window exists, return an empty string.”

Stressing duplicates must be covered upfront shows you’ve read the constraints carefully.

Step 1: Start With the Brute Force (Then Dismiss It)

The Key Insight — Expand Then Shrink

The formed / required Trick — The Heart of This Problem

“When the window frequency of a character equals its frequency in t, I increment formed. When I shrink the window and a character’s count drops below the required frequency, I decrement formed. Checking formed == required is O(1) — no need to scan the map.”

Step 3: Explain the Algorithm in Plain English

“I build a frequency map for t. I use two pointers — left and right — both starting at 0. I move right forward, adding characters to the window’s frequency map and updating formed when a character reaches its required count. When formed == required, the window is valid — I record it if it’s smaller than the best seen, then try to shrink by moving left forward. I keep shrinking while the window stays valid. Once it becomes invalid, I expand right again.”

Step 4: Talk Through the Code

from collections import Counter

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

        t_count  = Counter(t)           # Frequency map for t
        required = len(t_count)         # Unique chars in t that must be satisfied

        window_count = {}               # Frequency map for current window
        formed   = 0                    # Unique chars in window meeting required freq
        best     = float('inf'), 0, 0   # (window_size, left, right) of best window

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

            # Check if this char now meets its required frequency
            if char in t_count and window_count[char] == t_count[char]:
                formed += 1

            # Try to shrink the window while it remains valid
            while left <= right and formed == required:
                # Update best if this window is smaller
                if right - left + 1 < best[0]:
                    best = (right - left + 1, left, right)

                # Remove the leftmost character
                left_char = s[left]
                window_count[left_char] -= 1
                if left_char in t_count and window_count[left_char] < t_count[left_char]:
                    formed -= 1   # Window no longer satisfies this char

                left += 1

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

Point out the best tuple — storing (size, left, right) together avoids recomputing the window string until the very end, which keeps the inner loop clean.

Visual Walkthrough

Tracing s = "ADOBECODEBANC", t = "ABC". required = 3:

Full key steps trace:

Step 5: Highlight Edge Cases

Step 6: State Time and Space Complexity

Let m = len(s), n = len(t).

"In the worst case each character of s is added once when right moves and removed once when left moves — so the window processes at most 2m operations total. With the formed counter, the validity check inside the shrink loop is O(1). Overall O(m + n)."

Interview Checklist for Minimum Window Substring

• Restate — "smallest substring of s containing all chars of t including duplicates"
• Mention brute force O(m² · n) and dismiss it
• State the sliding window pattern — expand right until valid, shrink left to minimise
• Explain required — number of unique chars in t to satisfy
• Explain formed — counts satisfied unique chars, checked in O(1)
• Explain when formed increments and decrements
• Handle duplicate chars in t — frequency must be fully met
• Handle no valid window — return empty string
• Handle case sensitivity — uppercase and lowercase are distinct
• State O(m + n) time and O(m + n) space
• Ask before coding, don't just dive in

Related Problems to Practice

If you can solve Minimum Window Substring cleanly, try these next: