Longest Repeating Character Replacement
Given a string of uppercase letters and an integer k, you may change at most k characters. Return the length of the longest substring that can be made to consist of a single repeated letter.
- 1 ≤ s.length ≤ 10^5
- Uppercase English letters only
- 0 ≤ k ≤ s.length
- Longest *substring* with a replacement budget
- A window is valid when
length - maxFrequency ≤ k - Only 26 letters — cheap frequency table
A question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.
Keep a frequency table of the current window and the maximum frequency seen. A window of length w can be fixed with w - maxFreq replacements. Expand the right end; if w - maxFreq > k, slide the left end forward by one (decrementing that letter). The tracked maxFreq is allowed to be stale because the window only needs to grow when a new true maximum appears, so the final window length is the answer.
- Running the window once per target letter (26 passes) is easier to prove correct and still linear.