Fundamental Algorithms8 sections · 291 units
Open in Course

Longest Repeating Character Replacement - Key Insight

A window is valid if windowSize - maxFreq <= k. You keep the most frequent character and replace the rest.

1.1. Track frequency of each character in window.

2.2. Track the maximum frequency seen.

3.3. If windowSize - maxFreq > k, window is invalid. Shrink from left.

4.4. Update result with valid window size.

Key optimization: you don't need to decrease maxFreq when shrinking. A smaller window with a smaller max frequency won't beat the current best.