Minimum Window Substring

Hard#76variable size

You get two strings, s and t. Find the shortest piece of s, letters in a row, that contains every letter of t, as many times as t has it. If there is none, the answer is an empty string. Our example: s = "baxcab", t = "abc" — the answer is "cab".

76 Minimum Window SubstringWalkthrough · 1×

Example: s = "baxcab", t = "abc". Under s is need: how many of each letter the window still lacks. 0 is faded, below 0 means a spare.

0b1a2x3c4a5bneeda1b1c1missing–best–
not reached yet, still lackingwindowletter coming inletter going out, a spareleft the window, count 0covers t

Count the letters of t: the window has to collect {a: 1, b: 1, c: 1}

01/57
restart · back · play · step
Speed
1function minWindow(s, t):
2 need = count of each letter in t // missing keys: 0
3 missing = len(t)
4 left = 0
5 best = ""
6 for right from 0 to len(s) - 1:
7 if need[s[right]] > 0:
8 missing = missing - 1
9 need[s[right]] = need[s[right]] - 1
10 while missing == 0:
11 if best == "" or right - left + 1 < len(best):
12 best = s[left .. right]
13 need[s[left]] = need[s[left]] + 1
14 if need[s[left]] > 0:
15 missing = missing + 1
16 left = left + 1
17 return best
state
need
{a: 1, b: 1, c: 1}
missing
–
left
–
right
–
best
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. missing is the number of letters of t the window still lacks. It changes only when a count crosses 0, so "does the window cover t?" is answered in O(1) instead of comparing counts.
  2. A letter whose count is below 0 is a spare: dropping it keeps missing at 0. So the window shrinks past spares and letters t does not need, and stops only when it loses a letter it has to have.
  3. For every right the window is shrunk as far as it still covers t, so the shortest covering window ending at right is measured, and best keeps the shortest of them.

Complexity

Time O(n + m), where n and m are the lengths of s and t: t is counted once, and each letter of s comes into the window once and leaves at most once. Memory O(k) for the counts of k different letters.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.