Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Minimum Window Substring

LeetCode #76Hard
Smallest window of s covering all of t

Given strings s and t, return the smallest substring of s that contains every character of t, counting multiplicity. If no such window exists, return the empty string.

Asked atAmazonMetaLinkedIn
step 1 / 16
A
D
B
A
N
C
[0][1][2][3][4][5]
Expand + contract window
▸
1build need from t;  required ← distinct chars in t
2have ← 0;  window counts ← {}
3left ← 0;  best ← none
4for right ← 0 to n − 1:
5    add s[right] to window; if it now meets need: have++
6    while have == required:          // window is valid
7        if width < best: best ← [left, right]
8        remove s[left]; if it drops below need: have--
9        left++
10return best window
state
  • s"ADBANC"
  • t"ABC"
  • n6

line 1Find the SMALLEST window of s that contains every character of t, counting multiplicity. Here t = "ABC", so the window must hold at least one A, one B and one C.