Appearance
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.
Constraints:
- Length up to 100,000.
- 0 \le k \le s.length
Plain English: You are given a string of uppercase letters. You have a magic wand that can change at most k letters to any other letter. What is the longest contiguous block of identical letters you can create?
The naive approach
The brute-force way is to check every possible substring. For a given substring, count the frequency of all its letters. Find the letter that appears the most. If the length of the substring minus the frequency of that most common letter is \le k, it's a valid substring. Keep track of the maximum length found.
- Why it fails: Generating all substrings takes O(n^2). Counting frequencies for each takes O(n). Total time is O(n^3). With n = 100,000, this will TLE instantly.
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 ELI5 Analogy: Imagine you're trying to build a sports team from a group of kids, but you want them all to wear the same color jersey. You can only afford to buy k new jerseys. You look at a group of kids and see what color is already the most common. If 5 kids wear Red, 2 wear Blue, and 1 wears Green, the easiest way to make them all match is to keep the Red kids and buy new Red jerseys for the other 3. If you can only afford 2 new jerseys (k=2), you can't make this group match. You'll have to kick someone out of the group (shrink the window from the left) until the number of new jerseys you need fits your budget.
The solution
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 bestts
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;
}Code Walkthrough
count = {}: A hash map to store the frequencies of characters in our current window.max_count = 0: Tracks the historical maximum frequency of any single character we've seen in a valid window.count[s[right]] = ...: As the window grows to the right, we increment the frequency of the newly included character.max_count = max(...): We update our historical maximum if the new character's frequency breaks the record.while (right - left + 1) - max_count > k:: The core check.right - left + 1is the window size L. If L minus the most common character's frequency exceeds our budgetk, the window is invalid.count[s[left]] -= 1; left += 1: To fix the invalid window, we shrink it from the left. We decrease the count of the character falling out of the window and move theleftpointer.
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_countis 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.
Edge cases
- k \ge string length:
"AB", k=2. We can change everything. The answer is trivially the length of the string. - k = 0: We can't change anything. The problem just becomes "find the longest contiguous substring of identical characters." The window shrinks immediately when a different character enters.
- All identical characters:
"AAAA", k=2.maxCountequals the window size, soneedsis always 0, and the window grows to the end.
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.