Longest Repeating Character Replacement
Problem
You may change at most k characters in an uppercase string to any other uppercase letter. Return the length of the longest substring that can be made of one repeated letter after those changes.
Examples
Constraints
- • 1 <= s.length <= 10^5
- • s contains uppercase English letters only
- • 0 <= k <= s.length
Hints & approach
Hint 1
In a window, the cheapest fix is to keep the most frequent letter and change the rest.
Hint 2
A window is valid when its length minus its top letter count is at most k.
Hint 3
The top count never needs to decrease for the answer to stay correct.
Approachtry the hints first
Slide a window with letter counts and a variable maxFreq, the highest count seen in any window so far. Extend the right edge, update the count and maxFreq. If window length - maxFreq exceeds k, shift the left edge by one (decrementing its count). The window size never shrinks, and it only grows when a higher maxFreq appears, so the final window size is the answer.
Time O(n) · Space O(1) (26 counters)