76. Minimum Window Substring

HardSliding WindowSliding window + need counterShrinkable window covering a multiset requirement

Minimum Window Substring

Given strings s and t, return the shortest contiguous substring of s that contains every character of t including duplicates. If no such substring exists, return the empty string.

Open official problem prompt ↗

In plain English

Locate the tightest contiguous slice of s that still contains all letters of t, honoring duplicates.

Picture it like this

Dragging a shopping cart along a shelf: push the right edge until the cart holds every item on your list, then pull the left edge in to trim wasted shelf while the list stays complete.

Example

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Why: "BANC" is the shortest window of s that contains one A, one B and one C.

Constraints

m == s.lengthn == t.length1 <= m, n <= 10^5s and t consist of uppercase and lowercase English lettersThe answer is unique if it exists

Pattern lesson

See the pattern, then code

Shrinkable window covering a multiset requirement

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Grow the window until it contains all required characters, then shrink from the left as far as possible while it still contains them, recording the smallest such window.

New words, made simpleKnow these before the algorithm

need map: How many of each character are still required; can go negative when the window has surplus copies.
missing: Total count of required characters not yet covered; the window is complete when it reaches 0.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check every substring

Quadratic number of windows makes this infeasible for large inputs.

Enumerate all windows and test each against t's requirement.

Time O(m^2 * k)Space O(k)

Best choiceExpand-then-shrink sliding window

Each pointer sweeps s once, giving linear time.

Two pointers with a need counter; grow to satisfy, shrink to minimize, tracking the best.

Time O(m + n)Space O(k)

The rule we keep true

Invariant

Whenever missing == 0, the window from left to right contains at least the required count of every character in t.

Why this is correct

Reasoning

Expanding never removes coverage, so once missing hits 0 we have a valid window. Shrinking stops the instant a required character would drop below its needed count, so we always test the minimal valid window ending at the current right. Considering every right index guarantees the global minimum is seen.

The algorithm in three movesSay these aloud before coding

1Count required characters of t in a need map and set missing = len(t)

first full window 'ADOBEC' covers A,B,C

2Expand right: if the char was still required, decrement missing

shrinks; later window 'BANC' len 4 is smaller

3While missing == 0, record the window if it is the shortest so far, then release the left char and move left forward

best = 'BANC'

4Return the best window found (empty string if none)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

A10

N11

C12

1 · Readup to index 5 'ADOBEC'

2 · AskAre A,B,C all present?

3 · Update statemissing reaches 0

4 · Resultrecord window length 6

Key takeaway

Indices 9-12 spell BANC, the shortest window covering A, B and C.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-4Guard and count
Return empty for empty inputs; need counts t's characters; missing is the total still to cover.
2
Lines 8-11Expand right
Decrement missing only when the incoming char was genuinely still needed (need value positive).
3
Lines 12-18Shrink while complete
Record the shortest window, then release the left char; missing rises again once a required char count returns above zero.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

t longer than s returns empty string
Characters in t not present in s returns empty string
t has duplicate characters (e.g. 'AABC') which the count must honor
s equals t returns s

Common beginner mistakes

Ignoring duplicate requirements in t and treating need as a set
Decrementing missing for characters not in t (guard with need[ch] > 0 before decrement)
Off-by-one in the recorded window slice (store right+1 as the end)
Comparing window sizes before any valid window is found (initialize with an 'unset' end)

Check your understanding

Why can the need counter legitimately hold negative values?

PyPython 3 · solution.py

Optimal

1class Solution:2    def minWindow(self, s: str, t: str) -> str:3        from collections import Counter4        if not s or not t:5            return ""6        need = Counter(t)7        missing = len(t)8        left = 09        start, end = 0, 010        for right, ch in enumerate(s):11            if need[ch] > 0:12                missing -= 113            need[ch] -= 114            while missing == 0:15                if end == 0 or right - left + 1 < end - start:16                    start, end = left, right + 117                need[s[left]] += 118                if need[s[left]] > 0:19                    missing += 120                left += 121        return s[start:end]

Time complexityO(m + n)Optimized

Space complexityO(k) for the character counts (k distinct chars)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaAmazonGoogleUber

Minimum Window Substring

Minimum Window Substring

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window