424. Longest Repeating Character Replacement

The trick to this one is spotting which number decides whether a window is legal — and it isn’t the length. Once you see that a window works exactly when “everything but the majority letter” fits inside your budget of k replacements, the code writes itself. It’s a clean member of the sliding window pattern, and a good one to practice the grow-then-shrink rhythm on.

The problem

You get a string s of uppercase letters and an integer k. You may pick any positions and overwrite them with any letters, up to k changes total, and you want the longest run of a single repeated letter you can end up with. Return that length. (Full statement on LeetCode.)

Take s = "AABABBA", k = 1. Flip the lone A in the middle and you get "AABBBBA", whose "BBBB" block has length 4 — the best you can do here.

Intuition: length minus the majority is what you pay

Fix a window [left, right]. To turn it into one repeated letter, the smart move is to keep whichever letter already appears most inside that window and rewrite everything else. So the number of edits a window costs is:

$\text{cost} = (\text{window length}) - (\text{count of the most frequent letter})$

The window is achievable exactly when that cost is $\le k$. That single inequality is the whole problem. Slide right forward one letter at a time, and whenever the current window’s cost blows past k, drag left forward until it’s legal again. Every legal length you touch is a candidate answer.

There’s one detail that looks like a bug but isn’t: you never need to lower the tracked max frequency when the window shrinks. A stale, too-high max only ever makes the cost look smaller, so it can’t create a fake-valid window that beats the real best — the answer you’ve already recorded stands, and maxLen only grows when a genuinely longer valid window shows up. Skipping the recount keeps the whole thing at $O(n)$.

Solution

A size-26 array counts letters in the window, since the input is uppercase A–Z. left never moves backward, so each character enters and leaves the window at most once.

class Solution {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26];   // letter counts inside the current window
        int maxFreq = 0;            // highest single-letter count seen so far
        int best = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            int r = s.charAt(right) - 'A';
            freq[r]++;
            maxFreq = Math.max(maxFreq, freq[r]);

            // (window length) - maxFreq = letters we'd have to overwrite.
            // If that exceeds k, this window is illegal — shrink from the left.
            if ((right - left + 1) - maxFreq > k) {
                freq[s.charAt(left) - 'A']--;
                left++;
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }
}

Note the if, not a while: each step adds exactly one letter, so the window can only ever be one over budget, and a single shift on left holds its size steady. Be precise about what that shift does, though — with a stale maxFreq the window can remain technically over budget (feed it "AABABBA" with k = 1 and the window sitting over "ABAB" isn’t truly valid). What the single shift guarantees is that the window never grows past the best valid length already found, so best stays correct even when the current window isn’t. That’s exactly why the stale max is harmless and right - left + 1 is a safe read at the end.

Complexity

	Time	Space
Sliding window	$O(n)$	$O(1)$

left and right each march across the string once, so it’s linear. The frequency array is a fixed 26 slots regardless of input size, so space is constant.

In an interview

Say the cost formula out loud before writing anything: “a window is valid when its length minus its most common letter is at most k.” That one line proves you found the invariant, which is the part being graded — the loop is mechanical after that. The question interviewers love to poke at is exactly the stale-max concern, so get ahead of it: explain that a lingering high maxFreq can only under-count the cost, never fabricate a longer valid window, so recounting on shrink is wasted work.

Two easy traps: don’t reset maxFreq when left advances, and don’t reach for a while loop to shrink — a single if is enough here because you only ever add one letter per step. This grow-and-shrink shape is the backbone of the whole sliding window pattern, where the same window-validity idea drives problems like longest-substring and minimum-window questions.

References

• LeetCode 424 — Longest Repeating Character Replacement