DevOps NetworkDevOpsNetwork
Join Free
Advanced

Minimum Window Substring

hardHard arrays and strings Must-do

Problem statement

Given strings s and t, return the shortest contiguous substring of s that contains every character of t, including repeats: if t has two as, the window needs at least two as. If no such substring exists, return the empty string "".

Characters are case-sensitive letters. When several windows share the shortest length, return the one that starts first.

Examples

Example 1

Input: s = "xaybzcab", t = "abc"

Output: "cab"

Explanation: Windows like "aybzc" and "bzca" also contain a, b and c, but "cab" at the end is the shortest.

Example 2

Input: s = "aab", t = "aaa"

Output: ""

Explanation: s has only two as, so no window can hold three.

Hints

Approach

Sliding window with a satisfied counter. Let need count the characters of t, and required be the number of distinct characters in it. Move a right pointer r across s, adding each character to window. When window[c] reaches exactly need[c], one more character type is satisfied, so increment formed.

While formed == required the window is valid: record it if it's the shortest so far, then remove s[l] from the left. If that drops window[s[l]] below need[s[l]], decrement formed; either way move l right. Keep shrinking until the window stops being valid.

Each pointer moves across s once, so the work is linear. Record only strictly shorter windows to keep the earliest one on ties.

ComplexityTime O(n + m)Space O(σ)
Python
from collections import Counter
def min_window(s, t):
need = Counter(t)
required = len(need)
window = Counter()
formed = 0
best_len, best_start = float("inf"), 0
l = 0
for r, ch in enumerate(s):
window[ch] += 1
if ch in need and window[ch] == need[ch]:
formed += 1
while formed == required:
if r - l + 1 < best_len:
best_len, best_start = r - l + 1, l
left = s[l]
window[left] -= 1
if left in need and window[left] < need[left]:
formed -= 1
l += 1
return "" if best_len == float("inf") else s[best_start:best_start + best_len]
print(repr(min_window("xaybzcab", "abc")))
print(repr(min_window("aab", "aaa")))

Follow-up questions

  • Return the shortest window that contains t as a subsequence, in order (Minimum Window Subsequence, a DP or two-pass scan).
  • s is a live stream too large to store. How do you report the best window found so far?

Frequently asked questions

It is the hardest standard sliding-window problem, and sliding windows are how you reason about bounded ranges in streams: the shortest time span in a log that contains every error type, or the tightest window that saw events from all regions. Interviewers use it to check that you can maintain a validity condition incrementally rather than recomputing it.

formed counts character types that just became satisfied. With ==, each type increments formed exactly once, at the moment it reaches its target, and extra copies don't count again. With >=, a surplus character would inflate formed and the window would look valid too early.

For a character not in t, need[c] is 0. Its window count goes 0 → 1 on the way in, which never equals 0, and 1 → 0 on the way out, where the check compares the old value 1 with 0. Neither changes formed, so no special case is needed.