Longest Repeating Character Replacement
Longest Repeating Character Replacement is a medium Sliding Window problem from the Blind 75. The key pattern is sliding window with max count, and a good solution runs in O(n) time.
Problem
Given an uppercase string and k, return the longest substring that can be made one repeated character after at most k replacements.
Examples
Example 1
Input
{"text":"AABCCBB","k":2}Output
5Example 2
Input
{"text":"BABA","k":1}Output
3Example 3
Input
{"text":"A","k":0}Output
1Approach
Keep letter counts in the window and the highest single count seen. Shrink from the left whenever window length minus that count exceeds k.
| Pattern | Sliding window with max count |
|---|---|
| Time | O(n) |
| Space | O(26) |
Watch out for
The stored max count never needs to decrease; the answer only grows when it does.