LeetCode #76 Hard

Minimum Window Substring

Return the shortest substring of s containing every character of t, including duplicates. Return the empty string if none exists.

sliding-windowstringshashingtwo-pointers

Open on LeetCode ↗

02

Intuition

💡

Two phases alternating: grow the right edge until the window contains everything t requires, then pull the left edge in as far as possible while it still does. Record the length each time the window is valid and minimal. The efficiency hinges on making the validity check O(1) — rather than re-scanning the frequency map after every move, keep a counter formed of how many distinct required characters have reached their required multiplicity. The window is valid exactly when formed equals the number of distinct characters in t.

03

Approach

1

Build the requirement map

Count the characters of t, including duplicates: t = "AABC" requires two As. Let required be the number of distinct characters. This distinction matters — the window must satisfy every character's full count, but formed tracks how many characters have been fully satisfied, not how many total characters have been seen.

2

Grow until valid, tracking formed in O(1)

Advance the right edge, incrementing the window's count for each character. When a character's window count exactly equals its required count, increment formed. Using equality rather than >= is essential: a fourth A when only two are needed must not increment formed again. When formed == required the window contains everything.

3

Shrink while valid, then break validity and resume

Once valid, pull the left edge inward. Each removal decrements a count; when a required character's count drops below its requirement, decrement formed and stop shrinking. Before each removal, if the current window is shorter than the best recorded, update the answer. Then resume growing the right edge. Every index is touched at most twice — once by each pointer — so the whole algorithm is O(|s| + |t|).

04

Solution & live demo

python

▶1class Solution:
▶2    def minWindow(self, s, t):
▶3        if not s or not t:
▶4            return ""
▶5        need = {}
▶6        for ch in t:
▶7            need[ch] = need.get(ch, 0) + 1
▶8        required, formed = len(need), 0
▶9        have = {}
▶10        left, best = 0, (float('inf'), 0, 0)
▶11        for right, ch in enumerate(s):
▶12            have[ch] = have.get(ch, 0) + 1
▶13            if ch in need and have[ch] == need[ch]:
▶14                formed += 1
▶15            while formed == required:
▶16                if right - left + 1 < best[0]:
▶17                    best = (right - left + 1, left, right)
▶18                lc = s[left]
▶19                have[lc] -= 1
▶20                if lc in need and have[lc] < need[lc]:
▶21                    formed -= 1
▶22                left += 1
▶23        return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]

05

Edge cases

t longer than s

The window can never satisfy every requirement, formed never reaches required, and the empty string is returned.

Duplicate characters in t

The requirement map stores counts, and formed only increments on exact equality, so a window with one A does not satisfy a requirement of two.

s == t

The whole string is the answer; the window becomes valid at the last character and cannot shrink.

Characters in s not present in t

They are tracked in the window counts but never affect formed, so they are freely discarded during the shrink phase.

06

Complexity

Time

O(|s| + |t|)

Space

O(|s| + |t|)

Each index is visited at most twice. The maps hold at most the alphabet size, so the space is effectively constant for fixed alphabets.