Sliding window

Episode 20 Longest Repeating Character Replacement

6 min · LeetCode 424 · Java

Title card of Episode 20: Longest Repeating Character Replacement

▶ This video is coming to YouTube soon.

LeetCode 424, Longest Repeating Character Replacement, solved on screen. Three examples show the cases: change every other letter, pick the best substring, and k = 0, where the answer is just the longest run. Then the brute force checks every substring with a running count, and we read its O(n²) code line by line. Finally, a sliding window grows to the right and slides when it needs more than k changes: O(n). We also see why maxCount never has to go down.

What you'll learn

  • What the problem asks, through three worked examples
  • The key test: a window works if length − maxCount ≤ k
  • The brute force: every substring, O(n²) time, O(1) space
  • The sliding window with an int[26] count: O(n) time, O(1) space
  • Why a stale maxCount still gives the right answer

Chapters

  1. 0:00The problem
  2. 0:15Examples
  3. 0:52Brute force, visualized
  4. 1:45Brute force: the code
  5. 2:04Brute force, line by line
  6. 3:08Sliding window: the idea
  7. 3:31Sliding window, visualized
  8. 4:27Sliding window: the code
  9. 4:43Sliding window, line by line
  10. 5:46Comparing the approaches