4.6.3 — Longest Repeating Character Replacement

LeetCode 424 · Medium · ★ Blind 75

The problem

You may change up to k characters of the string to any other uppercase letter. Return the length of the longest stretch you can make into a single repeated character.

s = "ABAB", k = 2   →  4    (change both A's to B, or both B's to A)
s = "AABABBA", k=1  →  4    ("AABA" → change the B, giving "AAAA")

Only uppercase English letters.

The pattern

A window is valid if you can turn it into one repeated letter with at most k changes.

Work out how many changes a window needs. If the window has length L and its most common letter appears maxCount times, then everything else must be changed:

\text{changes needed} = L - \text{maxCount}

So the window is valid when L - maxCount <= k.

That is the whole condition. Extend right always; while L - maxCount > k, shrink from the left.

The solution

PythonTypeScript

python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        left = 0
        max_count = 0
        best = 0

        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
            max_count = max(max_count, count[s[right]])

            while (right - left + 1) - max_count > k:
                count[s[left]] -= 1
                left += 1

            best = max(best, right - left + 1)

        return best

function characterReplacement(s: string, k: number): number {
  const count = new Map<string, number>();
  let left = 0, maxCount = 0, best = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    count.set(c, (count.get(c) ?? 0) + 1);
    maxCount = Math.max(maxCount, count.get(c)!);

    while ((right - left + 1) - maxCount > k) {
      count.set(s[left], count.get(s[left])! - 1);
      left++;
    }

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

  return best;
}

The line that looks like a bug

max_count is never lowered when the window shrinks. After dropping a character from the left, the true most-common count may be smaller than max_count says. The code carries a stale number on purpose.

It is still correct, and here is why.

best only grows when a window is longer than every window before it. To beat the current best, a new window needs a larger maxCount than any window that came before — a smaller one cannot produce a longer valid window.

So if max_count is stale and too large, the condition L - max_count > k is too lenient, and the window is allowed to stay bigger than it should. But best does not grow either, because best is already at least that size. The stale value can only ever fail to shrink a window that was never going to improve the answer. The moment a genuinely better window appears, its maxCount really is larger, and max_count is updated to it on the line above.

Two consequences worth stating:

The window never shrinks below the best length found so far, so it moves like a ruler sliding along the string.
The value in max_count is not always the true maximum of the current window. It is a high-water mark. That is fine here and would not be fine if the problem asked you to report it.

If this makes you uncomfortable, recompute it honestly with max(count.values()) inside the loop. That is $O(26)$ per step, so still $O(26n) = O(n)$ , and it is easier to defend. Many strong candidates write that version deliberately.

Trace

s = "AABABBA", k = 1

right	char	window	counts	maxCount	needs	action	best
0	A	`A`	A:1	1	0	ok	1
1	A	`AA`	A:2	2	0	ok	2
2	B	`AAB`	A:2 B:1	2	1	ok	3
3	A	`AABA`	A:3 B:1	3	1	ok	4
4	B	`AABAB`	A:3 B:2	3	2 > 1	shrink once	4
5	B	`ABABB`	A:2 B:3	3	2 > 1	shrink once	4
6	A	`BABBA`	A:2 B:3	3	2 > 1	shrink once	4

Answer 4.

Complexity

$O(n)$ time. left only moves forwards, so it advances at most n times in total across the whole loop.

$O(1)$ space — at most 26 counts.

The general shape this belongs to

This is the "at most k of something" window, and it is one of the two most common window conditions.

Longest substring with at most k distinct characters → shrink while the map has more than k keys.
Longest subarray with at most k zeros (Max Consecutive Ones III) → shrink while the zero count exceeds k. That problem is this one with a two-letter alphabet, which is a good way to check you understood it.
Longest subarray with sum at most k, for non-negative numbers → shrink while the sum is too big.

The last one has a condition attached that matters: shrinking must reliably make the window more valid. With non-negative numbers, removing an element cannot increase the sum, so shrinking always helps. Add negative numbers and that stops being true, the window technique breaks, and you need prefix sums with a hash map instead. That is the precondition to check before reaching for a window.

What the interviewer will push on

"Why is the window valid check length - maxCount <= k?" Keep the most common letter and change everything else. There is no better choice, since keeping any other letter would mean changing more.

"Your maxCount is never decreased. Is that a bug?" The argument above. This is the question this problem exists to ask, and it comes up almost every time.

"What if the alphabet were not just 26 letters?" The count map still works. Only the $O(1)$ space claim changes, to $O(k)$ for k distinct characters.

"What if you had to return the actual substring?" Record left whenever best is updated.

One thing to volunteer: mention that this is the same problem as Max Consecutive Ones III with a two-letter alphabet. Connecting two problems that look unrelated is a strong signal.

Next: 4.6.4 Permutation in String — a window of fixed size, which changes the shape of the loop.

4.6.3 — Longest Repeating Character Replacement ​

The problem ​

The pattern ​

The solution ​

The line that looks like a bug ​

Trace ​

Complexity ​

The general shape this belongs to ​

What the interviewer will push on ​