Longest Repeating Character Replacement
Problem statement
You are given a string s made only of uppercase English letters, and a
budget k. You may pick up to k characters anywhere in the string and
change each one to any other uppercase letter.
Return the length of the longest substring you can turn into a single
repeated letter, using at most k of those changes.
Examples
Example 1
Input: s = "ABAB", k = 2
Output: 4
Explanation: Change both As to B (or both Bs to A) and the whole
Example 2
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Change the single A in the middle to B, giving
Hints
Approach
Optimal: Sliding window, no shrink
Intuition
Here's the trick: you don't actually need the window to shrink back to being
valid at every step. You only care about the longest window you ever
manage to build, and a window can never grow past the best one already found
unless it becomes at least that good again. So instead of shrinking with a
while loop, just check once: if the window is too expensive, slide it by
exactly one step (drop the oldest letter, move left forward by one) and
move on. The window's size then either grows or stays exactly the same size
it was before — it can never shrink from where it "peaked" — so tracking
right - left + 1 after this single check gives the correct answer at the
end.
The key detail: the running maxCount you keep is a high-water mark. It
records the highest letter frequency ever seen while the window was expanding
— it never decreases, even after letters are dropped. That sounds wrong, but
it isn't: an outdated maxCount can only make the check `(window) - maxCount
Notek
*stricter* than it truly needs to be, which can only stop the window from growing when it technically could have grown a little more — and by the time a real, longer valid window exists,maxCount` will have already grown to match it. It never lets an invalid window through.
Steps
- Start with
left = 0, an empty count array,maxCount = 0, andbest = 0. - For each
rightfrom0ton - 1:- Add
s[right]to the count array. - Update
maxCountto the larger of itself and the new count fors[right]. - If
(right - left + 1) - maxCount > k, the window is too expensive: drops[left]from the count array and moveleftforward by one (only once — no loop). - Update
bestwithright - left + 1.
- Add
- Return
best.
Dry run
s = "AABABBA", k = 1
| right | char | freq (A, B) | maxCount | window before check | valid? | action | window size | best |
|---|---|---|---|---|---|---|---|---|
| 0 | A | A:1 | 1 | 1 | yes | — | 1 | 1 |
| 1 | A | A:2 | 2 | 2 | yes | — | 2 | 2 |
| 2 | B | A:2, B:1 | 2 | 3 | yes | — | 3 | 3 |
| 3 | A | A:3, B:1 | 3 | 4 | yes | — | 4 | 4 |
| 4 | B | A:3, B:2 | 3 | 5 | no (5-3=2>1) | drop s[0]=A, left→1 |
4 | 4 |
| 5 | B | A:2, B:3 | 3 | 5 | no (5-3=2>1) | drop s[1]=A, left→2 |
4 | 4 |
| 6 | A | A:2, B:2 | 3 (stale) | 5 | no (5-3=2>1) | drop s[2]=B, left→3 |
4 | 4 |
maxCount freezes at 3 from step right = 3 onward, even though the count of
A in the current window later drops to 2 — that's the "high-water mark" from
the Intuition. The window size after each step never exceeds the best already
found, so the final best = 4 is correct.
Edge cases: k = 0 means no changes at all, so the answer is the length of
the longest run of one repeated letter already in s. k >= s.length means
every letter can be changed, so the answer is simply len(s).
Complexity
Time O(n) - each index enters and leaves the window at most once, and every step does a fixed, constant amount of work (one count update, one comparison to update the running maximum, and at most one letter dropped). There's no repeated scan of the 26 counts, which is what made the Better approach's constant factor larger.
Space O(1) - the same 26-slot count array.
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
counts = [0] * 26
left = 0
max_count = 0
best = 0
for right in range(len(s)):
idx = ord(s[right]) - ord('A')
counts[idx] += 1
max_count = max(max_count, counts[idx])
if (right - left + 1) - max_count > k:
counts[ord(s[left]) - ord('A')] -= 1
left += 1
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
print(Solution().characterReplacement("ABAB", 2)) # 4
print(Solution().characterReplacement("AABABBA", 1)) # 4RecapThe whole problem in a few lines, for the night before
- Spot it: longest substring that can become one repeated letter with at most k changes
- Idea: variable window; it is valid while window length - count of its most frequent letter <= k; otherwise move the left edge
- Cost: O(n) time, O(1) space (26 letters)
- Trap: the max frequency does not need to be lowered when the window shrinks; the answer only grows when a new higher max is found
Interview follow-ups
What if
kis at least as large as the length ofs?Then every letter can be changed if needed, so the whole string always qualifies and the answer is simply
len(s). The algorithm already handles this correctly without a special case: the window never needs to shrink, because(right - left + 1) - maxCountcan never exceedkwhenkis that large.Return the actual substring, not just its length.
Track
bestLeftalongsidebestand update both together whenever you find a new longest window:bestLeft = left. At the end, the answer substring iss[bestLeft : bestLeft + best]. This works even with the "no shrink" trick, becauseleftat the moment you record a new best is exactly the left edge of that window.The string arrives as a stream and doesn't fit in memory. How would you adapt this?
The algorithm already only looks at one character at a time and a 26-slot count array — it never needs the whole string in memory. Keep
left,right,maxCount,bestand the counts as running state, process each new character as it arrives, and drop the count fors[left]when the window slides. Memory stays O(alphabet size), completely independent of how long the stream runs.
Frequently asked questions
It sounds risky, but it isn't. maxCount is only ever used to decide whether
the current window still fits the budget. Letting it stay too high just
means the check is a little too strict, which can only make the algorithm
slide the window forward instead of letting it grow — it never lets an
actually-invalid window count toward the answer. And because the true answer
only comes from letters that are truly repeated close together, maxCount
will have already risen to the correct value by the time a genuinely longer
window appears.
The re-scan itself only looks at 26 numbers, which is a constant, not
something that grows with n. So each shrink step costs O(1), and there are
at most n shrink steps total (the left pointer moves forward at most n
times over the whole run). That keeps the total work at O(26·n), which
simplifies to O(n) — just with a larger constant factor than the Optimal
approach, which is why it's presented as a distinct, "correct but not yet
polished" step.
It's the same shape as tolerating a run of flaky results. Picture a stream of
health-check outcomes, U for up and D for down, and a budget of k
results you're willing to treat as "probably fine" (say, a known blip).
"What's the longest stretch I can call continuously healthy, allowing up to
k blips?" is exactly this problem, with two symbols instead of 26.
Swap the fixed 26-slot array for a hash map from character to count. The algorithm and its complexity stay the same — O(n) time, O(distinct characters) space — but a hash map's per-operation cost is O(1) only on average, not guaranteed, the way a small fixed array's is.
