Sliding window

Episode 23 Minimum Window Substring

6 min · LeetCode 76 · Java

Title card of Episode 23: Minimum Window Substring

▶ This video is coming to YouTube soon.

LeetCode 76, Minimum Window Substring, solved on screen. Three examples show what counts: the classic ADOBECODEBANC, a t with a repeated letter, and a t that s can't cover. The brute force checks every substring, O(m² · (m + n)). Then a sliding window with a need counter grows on the right until it covers t, and shrinks from the left while it still does, recording the shortest: O(m + n) time, O(1) space.

What you'll learn

  • What Minimum Window Substring asks, through three worked examples
  • The brute force: every substring, O(m² · (m + n)) time
  • need and missing: knowing in O(1) whether the window covers t
  • Grow right until the window covers t, shrink left while it still does
  • Why this window's while loop runs while the window is valid

Chapters

  1. 0:00The problem
  2. 0:17Examples
  3. 0:53Brute force, visualized
  4. 1:34Brute force: the code
  5. 1:49Brute force, line by line
  6. 2:38Sliding window: the idea
  7. 2:58Sliding window, visualized
  8. 3:55Sliding window: the code
  9. 4:16Sliding window, line by line
  10. 5:23Comparing the approaches