Longest Repeating Char Replacement LeetCode 424

LeetCode 424 Longest Repeating Character Replacement gives you a string s consisting of uppercase English letters and an integer k. Your task is to find the length of the longest substring you can obtain by replacing at most k characters in s so that all characters in the substring are the same.

The replacement operation lets you change any character in the substring to any other uppercase letter. You want to maximize the length of the resulting all-same-character substring. For example, with s = "AABABBA" and k = 1, the answer is 4 because you can replace one character in "AABA" or "ABAB" to get "AAAA" or "AAAB" — wait, specifically replacing the 'B' in "AABA" gives "AAAA", length 4.

This is a medium-difficulty problem that sits at the intersection of sliding window technique and frequency counting. The key insight is that you never need to know which characters to replace — you only need to know how many replacements are required, which is window length minus the count of the most frequent character in the window.

A window is valid when the number of characters you need to replace is at most k. The number of replacements needed equals the window size minus the count of the most frequent character in the window. In other words: replacements needed = (right - left + 1) - maxFreqInWindow. If this value is <= k, the window is valid.

Why does this formula work? Whatever the most frequent character is, keep all of those and replace everything else. The cost (number of replacements) is exactly window_size - max_frequency. If that cost fits within your budget k, the window can be made into an all-same-character string. If it exceeds k, the window is too large for the budget and must shrink.

This formula elegantly avoids needing to know which character is most frequent or which characters to replace. It reduces the problem to two values at every step: window size and max frequency in window. Both can be maintained incrementally as the window slides, making each step O(1).

The sliding window approach uses two pointers left and right, both starting at index 0. Expand right by one at each step, adding the new character to the frequency array. After expanding, check if the window is still valid using the formula. If it is invalid, move left forward by one, removing the leftmost character from the frequency array.

Unlike fixed-size windows, this window can grow and shrink. But crucially, the window never needs to shrink by more than one at a time. When the window becomes invalid (replacements > k), shrinking by one restores validity — or at worst keeps the window the same size. This means the window size is monotonically non-decreasing, which is the key to why the algorithm finds the maximum in O(n).

Track character frequencies with an integer array of size 26 indexed by character minus the character code of 'A'. Increment the slot for the new right character at each step, decrement the slot for the removed left character when shrinking. The maxFreq variable requires separate attention, as discussed next.

The most surprising aspect of this algorithm is that maxFreq never needs to be decreased, even when the window shrinks and the most frequent character may have been partially removed. This seems wrong at first — if the most frequent character count drops, shouldn't maxFreq reflect that? The answer is no, because of a subtle but powerful invariant.

The invariant is this: we only care about finding a window LONGER than the best we have seen so far. A window of the current size is valid if and only if maxFreq is at the current level. If shrinking causes the true max frequency to drop below the stored maxFreq, the window validity check (window_size - maxFreq > k) will still cause us to shrink — keeping the window the same size, not growing it. We never miss a longer valid window.

In practice this means maxFreq is a "lazy" maximum that only moves up, never down. The window grows only when a new character reaches a count exceeding the previous maxFreq, which is exactly when a longer valid window is possible. Any other expansion just slides at constant size — valid only by accident — but those don't contribute to the answer.

To correctly decrease maxFreq after shrinking, you would need to scan all 26 frequency slots to find the new maximum — O(26) per step. Over n steps, this is O(26n), which while technically O(n) is unnecessary overhead. The optimization avoids this entirely: simply never decrease maxFreq, and the algorithm remains correct.

The window grows only in two scenarios: either the window is already valid with the current maxFreq (so result updates), or a character's frequency exceeds maxFreq (so maxFreq increases and the window can stay valid at a larger size). In all other cases the window slides at constant size, which never worsens the answer.

This is an example of an amortized O(n) algorithm where the window pointer left never moves backward and right only moves forward — total O(n) pointer movements across all iterations. Combined with the O(1) per-step work (no 26-slot scan), the overall time complexity is O(n) with O(1) space for the 26-slot frequency array.

The Python solution is around 10 lines. Initialize freq = [0] * 26, left = 0, maxFreq = 0. Loop right from 0 to len(s) - 1: increment freq[ord(s[right]) - ord('A')], update maxFreq = max(maxFreq, freq[ord(s[right]) - ord('A')]). If (right - left + 1) - maxFreq > k: decrement freq[ord(s[left]) - ord('A')], increment left. Update result = max(result, right - left + 1). Return result. Total: O(n) time, O(1) space.

In Java, use int[] freq = new int[26]. The loop structure is identical. freq[s.charAt(right) - 'A']++ adds the right char; freq[s.charAt(left) - 'A']-- removes the left char when shrinking. The condition is (right - left + 1) - maxFreq > k. Java solution is equally concise — about 12 lines. Both languages benefit from the same invariant: maxFreq never decreases.

A common mistake is computing the answer only when the window is explicitly valid. This is unnecessary — you can just track result = max(result, right - left + 1) at every step, because the window size never shrinks below the previous maximum answer. The window is monotonically non-decreasing in size, so the last window size is always the maximum window size seen.

Longest Repeating Character Replacement belongs to the variable sliding window family — problems where the window size changes based on a budget or constraint. Its closest relative is Minimum Window Substring (LeetCode 76), which also uses variable windows and a "have vs need" counter. Both problems maintain a running measure of window validity and shrink when the constraint is violated.

Find All Anagrams in a String (LeetCode 438) is the fixed-size counterpart — the window always has exactly len(p) characters and slides one step at a time. Understanding fixed-size windows first makes the variable-size maxFreq trick here feel like a natural extension. The frequency array of size 26 appears in both, but the window management differs.

The Sliding Window Pattern guide covers the full family: fixed-size windows, variable-size with a budget (like this problem), and variable-size with a "contains all" requirement (like minimum window substring). Mastering LeetCode 424 gives you the variable-budget pattern that recurs in problems like Longest Subarray with Ones After Deletion (LeetCode 1493) and Max Consecutive Ones III (LeetCode 1004).