Minimum Window Substring

PracticeNeetCode ↗LeetCode ↗

Given two strings s and t, return the smallest substring of s that contains every character of t (matching duplicate counts too). Return an empty string if no such substring exists.

Example

Key Pointers

• This is a variable-size sliding window: expand the right edge to gather characters, then shrink the left edge as far as possible while the window still covers t.
• Track how many of t's distinct characters currently have their required count satisfied (formed), instead of comparing full count maps at every step.
• Every time the window fully covers t, that's a candidate for the smallest answer — try shrinking before expanding again.

Step-by-Step Analysis

1. Build a count map need from t, and let required be the number of distinct characters in it.
2. Expand right over s, updating a window count map; when a character's window count first matches its need, increment formed.
3. While formed == required: record the window if it's the smallest seen so far, then shrink from the left — decrement the count for s[left], and if that drops below its need, decrement formed.
4. Continue until right reaches the end of s.
5. Return the smallest window recorded, or an empty string if none was found.

Complexity

Time: O(|s| + |t|) — Space: O(|s| + |t|)

Code

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

    need = {}
    for ch in t:
        need[ch] = need.get(ch, 0) + 1
    required = len(need)

    window = {}
    formed = 0
    left = 0
    best_len = float('inf')
    best_left = 0

    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        if ch in need and window[ch] == need[ch]:
            formed += 1

        while formed == required:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_left = left

            left_ch = s[left]
            window[left_ch] -= 1
            if left_ch in need and window[left_ch] < need[left_ch]:
                formed -= 1
            left += 1

    return "" if best_len == float('inf') else s[best_left : best_left + best_len]

Code Explanation

How the solution above works, piece by piece.

1. need counts the letters of t; required is how many distinct letters must be satisfied.
2. Grow the window with right. When a letter's window count reaches exactly its need, one more requirement is met (formed += 1).
3. while formed == required: the window contains all of t. Record it if it's the shortest so far…
4. …then shrink from the left. If removing s[left] drops a needed letter below its count, the window is no longer valid and growing resumes.
5. Both pointers only move forward, so every character is added and removed at most once: O(|s| + |t|) time.

Visual Walkthrough

Running it on s = "ADOBECODEBANC", t = "ABC":

Video Explanation

NeetCode — Airbnb Interview Question, LeetCode 76