Longest Repeating Character Replacement — Walkthrough

Longest Repeating Character Replacement (#424) is one of the most popular medium-difficulty sliding window problems on LeetCode. It asks a deceptively simple question — given a string and a number k, find the longest substring where you can replace at most k characters to make every character in that substring the same.

What makes this problem special is the frequency twist. Unlike simpler sliding window problems where you just track a set of characters, this one requires you to maintain a frequency count inside your window and use it to decide when the window is valid. That single insight turns a confusing problem into an elegant O(n) solution.

If you have already solved Longest Substring Without Repeating Characters (#3), think of this as the harder sibling. Problem #3 asks you to avoid duplicates entirely. Problem #424 lets you have duplicates — but only if you can "fix" them within k replacements. The frequency optimization is what bridges the gap between the two.

You are given a string s consisting of uppercase English letters and an integer k. You can pick any character in the string and change it to any other uppercase English letter. You can perform this operation at most k times. Return the length of the longest substring containing the same letter after performing at most k replacements.

Consider the example s = "AABABBA" with k = 1. The answer is 4, because you can replace the single B at index 3 to get "AAAABBA" — a substring of length 4 with all A's. You could also replace the A at index 4 to get "AABBBBA" for a length-4 run of B's. Either way, the maximum is 4.

The brute-force approach would check every possible substring, count character frequencies, and determine if the substring can be made uniform within k replacements. That runs in O(n^2) or worse. The sliding window approach reduces this to O(n) by maintaining a window that expands and contracts as you scan the string from left to right.

The core insight is this: for any window of characters, the minimum number of replacements needed to make all characters the same equals the window size minus the count of the most frequent character. If that difference is less than or equal to k, the window is valid — you can replace all the minority characters to match the majority.

Formally, the validity condition is: windowSize - maxFrequency <= k. The windowSize is simply right - left + 1. The maxFrequency is the count of whichever character appears most often inside the current window. When this condition holds, you have a valid window. When it breaks, you need to shrink the window from the left.

This is what makes the sliding window frequency approach so powerful. You never need to actually perform the replacements. You just need to know whether the window could be made uniform with at most k changes. The frequency array gives you that answer in O(1) per step.

The implementation is clean and runs in O(n) time with O(1) space — the frequency array is always size 26 regardless of input length. You use two pointers, left and right, both starting at index 0. The right pointer expands the window one character at a time. After expanding, you check the validity condition and shrink from the left if needed.

Here is the step-by-step process: initialize a frequency array of 26 zeros, set left = 0, maxFreq = 0, and result = 0. For each right from 0 to n-1, increment the frequency of s[right]. Update maxFreq to be the maximum of maxFreq and the new frequency of s[right]. If (right - left + 1) - maxFreq > k, decrement frequency of s[left] and increment left. Finally, update result = max(result, right - left + 1).

Notice that you only shrink the window by one position at a time — not with a while loop. This is intentional and relates to the maxFrequency optimization explained in the next section. The result is always the maximum window size seen so far, and since the window only grows when maxFreq improves, the answer is correct.

This is the part that confuses almost everyone on their first encounter with this problem. When you shrink the window from the left, the character you remove might have been the most frequent one. So shouldn't you recalculate maxFrequency? The answer is no — and understanding why is the key to mastering this problem.

The reason is subtle: your answer can only improve when maxFrequency increases. If maxFreq stays the same or decreases, the best window size you can achieve is no better than what you have already recorded. By not decrementing maxFreq, you effectively keep the window at its current best size and only allow it to grow when a new character frequency exceeds the old maxFreq.

Think of it this way: maxFreq acts as a high-water mark. When it goes up, you can potentially fit a larger valid window. When it stays flat, the window stays the same size — it slides but does not shrink. This means some windows you examine are technically invalid, but that does not matter because you already recorded the best valid answer at the previous maxFreq level.

This optimization turns a potential O(n) recalculation per step into O(1), keeping the entire algorithm at O(n). Without it, you would need to scan the frequency array every time you shrink the window, adding an inner loop that could degrade performance.

There are several edge cases worth considering before you submit. First, when k = 0, you cannot make any replacements. The answer reduces to finding the longest run of a single repeating character — essentially the longest contiguous substring of identical characters. The sliding window still works because the validity condition becomes windowSize - maxFreq <= 0, which means the window must be entirely one character.

Second, when k is greater than or equal to the string length, every character can be replaced. The answer is simply the length of the string, since you can turn the entire string into any single character. Your algorithm handles this naturally — the window never needs to shrink because the validity condition is always satisfied.

Third, if the string consists of all the same character (like "AAAA"), the answer is the full length regardless of k. Again the algorithm handles this because maxFreq equals the window size at every step, so windowSize - maxFreq is always 0.

Longest Repeating Character Replacement is a gateway problem for the sliding window with frequency tracking pattern. Once you internalize the validity condition — windowSize minus maxFrequency must not exceed k — you can apply the same framework to a family of related problems. Minimum Window Substring (#76), Permutation in String (#567), and Find All Anagrams in a String (#438) all use variations of the same technique.

The maxFrequency optimization teaches an even deeper lesson: sometimes you do not need perfect bookkeeping. In many sliding window problems, maintaining a "good enough" invariant is sufficient because the answer only improves in one direction. This idea appears again in problems like Longest Substring with At Most K Distinct Characters (#340) and Subarrays with K Different Integers (#992).

If you found this problem challenging, review it with YeetCode flashcards to build pattern recall. The sliding window frequency pattern is one of the most commonly tested in coding interviews, and being able to recognize it instantly — and explain the maxFreq optimization — will set you apart from other candidates.