Longest Repeating Character Replacement
A window is valid while (length − count of its most frequent char) ≤ k.
Sliding Window Trace
Problem
Given an uppercase string and a replacement budget k, find the maximum length of a contiguous substring that can be transformed into a string of one repeated character by changing at most k characters. Return only the length of that longest possible window.
Examples
Input: s = "AABABBA", k = 1
Output: 4
Input: s = "ABAB", k = 2
Output: 4
A characters to B, or both B characters to A, so the entire string can become uniform.The Goal
Find the longest stretch of s you can turn into one repeated letter by changing at most k letters.
Keep the window's commonest letter and change the rest. If maxFreq is that letter's count, a window of length L costs L - maxFreq changes. It's valid when that's at most k.
For AABA, the cost is 4 - 3 = 1.
Count changes, not target letters
The best letter to keep is the one the window already has most of.
Valid when L - maxFreq <= k.
Key Idea: Grow, Then Repair
Move right one letter at a time and add it to the counts. If the window now costs more than k, drop letters from the left until it doesn't.
Both pointers only move forward, so each letter enters once and leaves at most once.
For AABAB with k = 1, the cost is 5 - 3 = 2. Dropping the first A leaves a window of 4, which passes the check because maxFreq is still 3.
A window of length L needs L - maxFreq changes.
AABA: 4 - 3 = 1.
The Algorithm
Update the counts as the window moves instead of recounting it. Raise maxFreq whenever the new letter's count beats it.
counts = empty frequency map
left = 0
maxFreq = 0
best = 0
for right from 0 to n - 1:
counts[s[right]] += 1
maxFreq = max(maxFreq, counts[s[right]])
while (right - left + 1) - maxFreq > k:
counts[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestAdd the new letter before you check, and record best only after the window passes.
| Approach | Time | Space | Catch |
|---|---|---|---|
| Sliding window | O(n) | O(1) | Each pointer moves forward once |
| Recount every window | O(n^2) | O(1) | Repeats the counting |
| Try each target letter | O(26n) | O(1) | Works, but takes 26 passes |
Walkthrough
Run it on AABABBA with k = 1.
The window grows to AABA, which costs 4 - 3 = 1, for a best of 4. Each later letter pushes the cost to 2, so one letter drops from the left and the window slides on at length 4.
The answer is 4.
Checkpoint · predict the next step
Step 6 of 12 on the stage: Add 'B' (now 2 in the window). 5 − maxFreq 3 = 2 > 1: too many replacements.
window "AABAB" (left 0, right 4) · k 1 · maxFreq 3 · length 5 · best 4
Pitfalls
maxFreq never goes down. After AABAB shrinks to ABAB, the true count is 2, but maxFreq still says 3.
That's safe. A stale count can pass a window that really needs more than k changes, but that window is never longer than a real one you've already found. So best stays right, and you never rescan the 26 counts.
Do decrement the letter you drop, or every later count is off.
After a drop, why is it safe to leave maxFreq too high?
Complexity
There's a loop inside a loop, but it's still O(n): right crosses each letter once, and left crosses each at most once. The counts cover 26 letters, so space is O(1).
Because maxFreq never drops, the window never shrinks. It only grows or slides, so one drop per step is always enough.
Two forward pointers
- Expand rightEach letter enters once.dominantO(n)
- Shrink leftEach letter leaves at most once.dominantO(n)
- Letter counts26 uppercase letters.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Linear time, constant space.
In short
Slide a window tracking character counts and the max single-character count inside it. If the window's length minus that max exceeds k, too many replacements are needed — shrink from the left. The widest valid window is the answer.
Common mistake
Recomputing the true max frequency on every shrink; you can let a slightly stale max stand because the window only ever needs to grow past its best.