LeetCode 76 · Hard · Sliding Window

Minimum Window Substring

Given strings s and t, return the shortest substring of s that contains every character of t, duplicates included. Return "" if no substring does.

O(n + m)time
O(k)space · distinct letters
have == needgrow, then shrink

letters A–Z and a–z, case-sensitive · s: 1–20 · t: 1–6

window vs countT per letter of t: count in the window / count needed · green = satisfied · dashed outline = shortest valid window so far

public String minWindow(String s, String t) { if (t.isEmpty()) { return ""; } int[] countT = new int[128]; int[] window = new int[128]; int need = 0; for (char c : t.toCharArray()) { if (countT[c]++ == 0) { need++; } } int have = 0; int resL = -1; int resR = -1; int resLen = Integer.MAX_VALUE; int l = 0; for (int r = 0; r < s.length(); r++) { char c = s.charAt(r); window[c]++; if (countT[c] > 0 && window[c] == countT[c]) { have++; } while (have == need) { if (r - l + 1 < resLen) { resL = l; resR = r; resLen = r - l + 1; } char left = s.charAt(l); window[left]--; if (countT[left] > 0 && window[left] < countT[left]) { have--; } l++; } } if (resLen == Integer.MAX_VALUE) { return ""; } return s.substring(resL, resR + 1);}
l
—
r
—
have / need
—
window
—
resL, resR
—

Why it works

  1. Brute force checks every substring against the counts of t: O(n²) substrings with an O(k) check each.
  2. Grow until valid, then shrink while valid. Move r until the window covers t. Then drop from the left, recording the length each time, until it stops covering. Every minimal window is seen at the moment just before the shrink breaks it.
  3. Count letters, not characters. have counts the distinct letters whose window count reached what t needs. It changes only when a count crosses its target, so the validity test have == need is O(1).
  4. Why O(n + m): l and r each move at most n times, and building countT reads t once.
  5. Pitfall: duplicates in t matter. For t = "aa" the letter is satisfied only at count 2, and have drops when the count falls below 2, not to 0.