visual walkthrough
Longest Repeating Character Replacement
The 'window length − max frequency ≤ k' invariant is a classic insight.
The idea
In any window, the cheapest plan is to turn every letter into the most common one. The number of changes is the window's length minus the count of that most common letter; the window is valid if that is at most k.
Slide a window to the right and shrink it from the left whenever it needs more than k changes. The largest valid window seen is the answer.
Complexity
| approach | time | space |
|---|---|---|
| Check every substring | O(n³) | O(1) |
| Sliding window | O(n) | O(1) |