Longest Repeating Character Replacement

This problem hides its window behind a rule about replacements. Once you see how many changes a given stretch needs, it becomes a standard longest window. It is also famous for a trick in the fast version, and interviewers often ask you to justify it.

The problem

You get a string of uppercase letters and a number k. You may change up to k characters to any other uppercase letter. Return the length of the longest stretch you can make consist of a single repeated letter.

• s = "ABBCBBA", k = 1 → 5. Change the C in "BBCBB" to B and you get five Bs in a row.
• s = "ABCD", k = 0 → 1. No changes allowed, and no letter repeats next to itself.

Constraints: 1 ≤ length ≤ 10⁵, 0 ≤ k ≤ length.

Clarifying questions

• Uppercase English letters only? Yes, so there are 26 possible letters.
• Must I use all k changes? No, "at most k".
• Return the length or the stretch? The length.

Approach 1: every start, growing to the right

For a fixed start, grow the end one step at a time, keeping letter counts and the largest count seen. A stretch can be made uniform if the letters that are not the most common one number at most k. Record every stretch that qualifies.

1def replacement_brute(s: str, k: int) -> int:2    """Every start, grow right with running counts: O(n^2)."""3    best = 04    for start in range(len(s)):5        counts = [0] * 266        top = 07        for end in range(start, len(s)):8            counts[ord(s[end]) - 65] += 19            top = max(top, counts[ord(s[end]) - 65])10            if (end - start + 1) - top <= k:11                best = max(best, end - start + 1)12    return best

Time: O(n²). Space: O(1). At n = 10⁵ that is 5 × 10⁹ inner steps, far too slow.

The key insight

Look at one stretch. To make it all one letter at the lowest cost, keep its most common letter and change everything else. So the number of changes it needs is:

changes needed = window length − count of the most common letterthe window is valid when   changes needed <= k

That formula is the whole problem. Derive it rather than memorising it; it takes twenty seconds.

And it has the property a window needs. If a stretch needs more than k changes, any longer stretch containing it needs at least as many, because adding a letter adds one to the length and at most one to the top count. So as end moves right, start only ever needs to move right too. This is a longest window: expand, shrink while length − top > k, record.

Approach 2: a window with the true maximum

Keep a count for each letter in the window. The most common count is max(counts), a scan of 26 slots.

1def replacement_window(s: str, k: int) -> int:2    """Window valid while length - max(counts) <= k. O(26 n)."""3    counts = [0] * 264    start = 05    best = 06    for end, char in enumerate(s):7        counts[ord(char) - 65] += 18        while (end - start + 1) - max(counts) > k:9            counts[ord(s[start]) - 65] -= 110            start += 111        best = max(best, end - start + 1)12    return best

This is correct and O(26n), which is fine for n = 10⁵. It is a good answer. But interviewers often push for the version that avoids the 26-slot scan.

Approach 3: a maximum that never decreases

Replace max(counts) with a variable max_count: the largest count any letter has reached in any window so far. Update it only upward when a letter enters. Never lower it when a letter leaves.

1def character_replacement(s: str, k: int) -> int:2    """Window valid while length - max_count <= k; max_count never decreases."""3    counts: dict[str, int] = {}4    start = 05    max_count = 06    best = 07    for end, char in enumerate(s):8        counts[char] = counts.get(char, 0) + 19        max_count = max(max_count, counts[char])10        while (end - start + 1) - max_count > k:11            counts[s[start]] -= 112            start += 113        best = max(best, end - start + 1)14    return best

Why a stale max_count is safe. After a shrink, max_count may be larger than any count in the window. That makes the rule easier to pass, so the window may keep a size it should not. But look at what that means: the window never shrinks below the best length found so far; it just slides forward at that size. The answer can only grow when length − max_count <= k holds with a larger length, and since max_count only grows when a letter really reaches that count, a larger answer is only ever recorded for a window that really is valid. So the stale value can never produce a wrong, too-large answer.

Dry run on "ABBCBBA", k = 1:

At end = 6 the window BCBBA really needs 2 changes, more than k. With the stale max_count = 4 it looks valid, so it slides at length 5 instead of shrinking. That is harmless: its length equals the best already recorded. Approach 2 would shrink to BBA here, and both return 5.

Time: O(n): each index enters once and leaves at most once, and there is no 26-slot scan. Space: O(1), at most 26 keys.

Because max_count never falls, the window's length never falls either, and the while body runs at most once per step. Many solutions write it as an if for that reason. It is correct here, but only because of the stale maximum; keep the while unless you can explain why.

Edge cases

• k = 0. The answer is the longest run of one letter already in the string.
• k at least the length. Every window is valid; the answer is the whole length.
• One letter only, "AAAA". max_count grows with the window; nothing is ever removed.

Follow-ups

• "Binary string: flip at most k zeros to get the longest run of ones." The same window with the rule "number of zeros in the window is at most k" (Max Consecutive Ones III).
• "Return which letter to repeat." Track the letter that set max_count when best improves.
• "Lowercase and uppercase mixed." Use a dictionary, or a 52-slot array; nothing else changes.