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.
Intuition
Ask what it costs to make a given window uniform. Keep whichever character already appears most often and change everything else, so the cost is window length - count of the most frequent character. The window is usable when that cost is at most k. That gives a clean validity test, and since shrinking a window never increases its cost, the standard grow-right / shrink-left sliding window applies.
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
Turn 'at most k replacements' into a window condition
For any substring, the cheapest way to make it uniform is to preserve its most common character and rewrite the rest. If the window has length L and its most frequent character appears maxFreq times, the number of replacements needed is L - maxFreq. So the window is achievable exactly when L - maxFreq <= k. This single inequality is the whole problem.
Grow right, shrink left when the cost exceeds k
Advance the right edge one character at a time, updating a frequency map. After each addition, check the cost. If it exceeds k, advance the left edge — decrementing frequencies as characters leave — until the window is valid again. Record the length after each step. Both pointers only move forward, so despite the nested loop the total work is O(n).
Note the maxFreq subtlety
Many implementations never decrease maxFreq when shrinking, which looks like a bug but is not: a stale, too-large maxFreq only makes the window look cheaper than it is, so it can never cause the recorded best to exceed a genuinely achievable length. The window can drift out of true validity, but the answer stays correct because the best length was already achieved earlier. Recomputing maxFreq honestly on shrink is also correct and easier to defend in an interview — with only 26 letters the recomputation is O(26) and does not change the complexity class.
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.