Problem Statement

Longest Repeating Character Replacement

You are given a string s made of uppercase letters, and a number k. You are allowed to change any letter into any other uppercase letter, and you can do this up to k times. The goal is to find the longest stretch of letters that are all the same after you make those changes. The tool we use here is a sliding window. A sliding window is like looking at a string through a small frame that you can stretch wider or pull in from the side. The left edge and the right edge of the frame mark the piece of the string we are studying right now. Here is the trick that makes this work: inside any window, the smartest move is to keep the letter that appears the most and change everything else into it. So the number of changes a window needs is the window's length minus the count of its most common letter. As long as that number of changes is k or fewer, the window is allowed. If it ever needs more than k changes, the window has grown too big and we pull the left edge in.

mediumSliding WindowSliding WindowTime: O(n) · Space: O(1)

Signals to notice

longest substring with at most k character replacementsvariable window with budgettrack most frequent character

Brute force first

Check every substring. Each substring independently checked. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Sliding window: track the frequency of the most common character in the window. If windowSize - maxFreq > k, shrink from left. Track maximum window size. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `s="AABABBA", k=1`

r=0 'A': count{A:1} maxFreq=1, size1-1=0<=1 ok, result=1
r=1 'A': count{A:2} maxFreq=2, size2-2=0<=1 ok, result=2
r=2 'B': count{A:2,B:1} maxFreq=2, size3-2=1<=1 ok, result=3
r=3 'A': count{A:3,B:1} maxFreq=3, size4-3=1<=1 ok, result=4
r=4 'B': count{A:3,B:2} maxFreq=3, size5-3=2>1 shrink: drop s[0]='A' count{A:2,B:2} left=1, size4, result=4
r=5 'B': count{A:2,B:3} maxFreq=3, size5-3=2>1 shrink: drop s[1]='A' count{A:1,B:3} left=2, size4, result=4
r=6 'A': count{A:2,B:3} maxFreq=3, size5-3=2>1 shrink: drop s[2]='B' count{A:2,B:2} left=3, size4, result=4
loop ends, return result=4

What must stay true

A window is valid if the number of characters to replace (windowSize - maxFrequencyInWindow) ≤ k. The optimal strategy is to keep the most frequent character and replace the rest. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

for right in 0..n-1:
    count[s[right]] += 1
    maxFreq = max(maxFreq, count[s[right]])
    if (right - left + 1) - maxFreq > k:   # too many to replace
        count[s[left]] -= 1; left += 1     # slide window forward
    result = max(result, right - left + 1)
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Recalculating maxFreq from scratch when the window shrinks — you don't need to. An overestimate of maxFreq never causes wrong answers because the window only grows when maxFreq truly increases. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Sliding Window Pattern