76. Minimum Window Substring

Return the shortest substring of s that contains every character of t (with multiplicity), or "" if there is none.

Expand right until the window covers t (tracked by a count of satisfied letters). Then shrink from the left as long as it still covers t, recording the smallest window.

1function minWindow(s: string, t: string): string {
2  const need = new Map<string, number>();
3  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
4  let have = 0, lo = 0, bestLo = 0, bestLen = Infinity;
5  const win = new Map<string, number>();
6  for (let hi = 0; hi < s.length; hi++) {
7    const c = s[hi];
8    win.set(c, (win.get(c) ?? 0) + 1);
9    if (win.get(c) === need.get(c)) have++;
10    while (have === need.size) {
11      if (hi - lo + 1 < bestLen) { bestLen = hi - lo + 1; bestLo = lo; }
12      const d = s[lo++];
13      win.set(d, win.get(d)! - 1);
14      if (need.has(d) && win.get(d)! < need.get(d)!) have--;
15    }
16  }
17  return bestLen === Infinity ? "" : s.slice(bestLo, bestLo + bestLen);
18}

need

s

t needs 3 distinct letter(s).

1 / 0

Space: play/pause · ←/→: step