Longest Repeating Character Replacement
Longest Repeating Character Replacement: you may change at most k characters of s to any other uppercase letter. Return the length of the longest substring consisting of a single repeated character that you can produce.
- 1 <= s.length <= 10⁵
- s consists of only uppercase English letters.
- 0 <= k <= s.length
Intuition
Longest repeating character replacement finds the longest substring achievable by changing at most k characters so all characters match. The window slides, but the validity condition is what carries the insight.
A window can be made uniform when the characters needing replacement number at most k. Those are exactly the characters that are not the window's most frequent one:
- A window is valid when windowLength − countOfMostFrequentCharacter <= k.
That single expression captures the whole problem. There is no need to decide which character to keep — the most frequent one is always the best choice, since it minimises the replacements required.
So the algorithm extends the right edge, updating a frequency count, and shrinks from the left whenever the window becomes invalid.
The part that surprises people is that the max-frequency count is never decreased when the window shrinks. That looks like a bug but is deliberate: a stale, too-high maximum only makes the window appear valid, and since the answer is a maximum length, a window can never shrink below the best already found. The result stays correct while avoiding a recount on every shrink.
Recomputing the true maximum after each shrink is also correct, just slower by a factor of 26 — worth preferring if the shortcut feels uncomfortable.
The window never shrinks below the best length seen, so the answer can simply be the final window size, though tracking the maximum explicitly is clearer.
With 26 uppercase letters, the frequency array is fixed size and the space is O(1).
A window is valid when windowLength - maxFreq <= k — the characters that aren't the most common one are exactly the ones you'd have to replace. The surprise is that maxFreq never needs to be decreased when the window shrinks; a stale-but-too-large value simply blocks growth until a genuinely better window appears.
Approach
Before reading on: price up what the direct approach costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(1) space.
State the validity condition
A window works when windowLength - maxFrequency <= k — the characters that are not the most common are exactly those needing replacement.
Always keep the most frequent character
No decision about which character to keep is needed. The most frequent one always minimises replacements, so the condition alone drives everything.
Extend the right edge
Move right one character at a time, incrementing its count and updating the running maximum frequency.
Shrink when invalid
While the condition fails, decrement the leftmost character's count and advance the left pointer until the window is valid again.
Leave the max frequency stale
Do not recompute the maximum when shrinking. A stale high value only makes windows look valid, and since the answer is a maximum, the result stays correct while saving work.
Track the longest valid window
Record the maximum window length seen. The window never shrinks below the best found, so the final size also works as the answer.
Cost of the scan
Each character enters and leaves the window once, giving O(n) time, with O(1) space for the fixed 26-letter frequency array.
Solution & live demo
Common pitfalls
Recomputing maxFreq after every shrink
count[s[left]] -= 1 left += 1 maxFreq = max(count.values())
count[s[left]] -= 1 left += 1
That's an O(26) scan per step for no gain. A stale maxFreq only ever makes the validity test stricter, so the window never grows past a genuinely invalid size — and the recorded best is still correct because it was recorded when the value was accurate.
Shrinking with if instead of while
if (right - left + 1) - maxFreq > k:
while (right - left + 1) - maxFreq > k:
Adding one character can only ever violate the condition by one, so if happens to work here — but it silently breaks the moment the pattern is reused with a condition that can be violated by more. while states the invariant honestly.
Measuring the window after moving left
left += 1 best = max(best, right - left + 1)
while ...:
left += 1
best = max(best, right - left + 1)The measurement belongs after the shrink loop has fully restored validity, not inside it. Measuring mid-shrink records a window that is either still invalid or smaller than the one you end up with.
Edge cases
Every character can be replaced, so the answer is the whole string length. The cost condition is never violated and the window never shrinks.
No replacements allowed, so the answer is the longest run of a single character — which the window finds, since any second distinct character immediately makes the cost 1.
maxFreq equals the window length, so the cost stays 0 and the window spans the whole string.
One iteration; the answer is 1.