Longest Repeating Character Replacement
Change at most k letters so that the longest possible run of one repeated letter appears, and return that run's length.
- Window with counts and a validity check
- Variable-size sliding window
Before this, know: Sliding window (Longest Substring Without Repeating Characters), Counting with a hash map (week 1)
You get a string s of capital letters and a number k. You may change any
letter into any other letter, at most k times. After your changes, what’s the
longest run of one repeated letter you can get? Return its length.
Example: s = "AABABBA", k = 1.
- A0
- A1
- B2
- A3
- B4
- B5
- A6
The rules that matter:
- A “run” is a substring: letters that sit next to each other.
- You can make at most
kchanges (fewer is fine).kcan be 0. - Only capital letters A to Z.
Let’s go very slowly here, because one small formula is the whole problem.
Take any stretch of letters, say "AABA". We want to turn all of it into the
same letter. Which letter should we keep? The one that appears most often,
because then we have the fewest letters to change.
"AABA"has 3 A’s and 1 B. Keep the A’s, change the 1 B. 1 change.- If we kept the B instead, we’d change 3 A’s. 3 changes. Worse.
So the number of changes a stretch needs is:
changes needed = length of the stretch − count of its most common letter
For "AABA": 4 − 3 = 1. We call “count of the most common letter” maxFreq
(the maximum frequency). The stretch is allowed if the changes needed fit in
our budget:
length − maxFreq ≤ k
change 1 ≤ k = 1: valid
Pause and think
"AABAB": 3 A’s and 2 B’s, so maxFreq = 3 and changes = 5 − 3 = 2. That’s more
than 1, so not allowed.
"BABB": 3 B’s and 1 A, so changes = 4 − 3 = 1 ≤ 1. Allowed: change the A and
you get "BBBB".
Check every substring: for each start, extend the end one letter at a time,
keep letter counts, and test length − maxFreq ≤ k. Keep the longest one that passes.
Brute force: every substring
s = "ABAB", k = 1
- A0
- B1
- A2
- B3
| letter | in window | |
|---|---|---|
| empty | ||
- window length
- —
- maxFreq
- 0
- to change
- —
- k
- 1
- best
- 0
- Inside the window
- Just added
- Window needs too many changes
- Just dropped
- Best window
Check every substring (every start, every end). For each one, count its letters and ask: is length − (count of the most common letter) ≤ k = 1?
Which line is running?
function characterReplacement(s, k) { let best = 0;Running now: for (let start = 0; start < s.length; start++) { const count = new Map(); // letter -> how many times it appears let maxFreq = 0; for (let end = start; end < s.length; end++) { count.set(s[end], (count.get(s[end]) ?? 0) + 1); maxFreq = Math.max(maxFreq, count.get(s[end])); if (end - start + 1 - maxFreq <= k) { best = Math.max(best, end - start + 1); } } } return best;}Brute force
function characterReplacement(s, k) { let best = 0; for (let start = 0; start < s.length; start++) { const count = new Map(); // letter -> how many times it appears let maxFreq = 0; for (let end = start; end < s.length; end++) { count.set(s[end], (count.get(s[end]) ?? 0) + 1); maxFreq = Math.max(maxFreq, count.get(s[end])); if (end - start + 1 - maxFreq <= k) { best = Math.max(best, end - start + 1); } } } return best;}def character_replacement(s, k): best = 0 for start in range(len(s)): count = {} # letter -> how many times it appears max_freq = 0 for end in range(start, len(s)): count[s[end]] = count.get(s[end], 0) + 1 max_freq = max(max_freq, count[s[end]]) if (end - start + 1) - max_freq <= k: best = max(best, end - start + 1) return bestA string of length n has about n × n ÷ 2 substrings. For "ABAB" that’s 10.
For 100,000 letters (LeetCode’s limit) it’s about 5 billion. That’s
O(n²). And we keep re-counting letters
that the previous substring already counted.
This is the same grow-and-shrink window as Longest Substring Without Repeating Characters. The difference is the rule: instead of “no repeats” (checked with a set), it’s “few enough changes” (checked with counts).
Pattern
Window with counts and a validity check
Use it when: a window is valid or not depending on how many of each item it contains, and you want the longest valid window.
Signal words
- “replace at most k”
- “longest substring with”
- “same letter”
- “at most k distinct”
- “after k changes”
- Start with an empty count map,
left = 0,maxFreq = 0,best = 0. - Move
rightfrom the first letter to the last. Adds[right]to the counts. - Update
maxFreqif this letter’s count is now the highest we’ve seen. - While
(right − left + 1) − maxFreq > k, the window needs too many changes: lower the count ofs[left]and moveleftright. - The window is now no longer than one we already know is valid (usually it is valid itself; see “Why we never lower maxFreq” for when it isn’t). Record its length in
bestif it’s the longest.
Watch the budget bar under the variables: green squares are letters we keep,
amber ones we’d change. It turns red when the changes needed go over k. Usually
that’s exactly when the window shrinks. The exception: when maxFreq is out of
date, the bar uses the real count and can stay red while the window just slides
(the next section explains why that’s fine).
Sliding window with counts
s = "AABABBA", k = 1
- A0
- A1
- B2
- A3
- B4
- B5
- A6
| letter | in window | |
|---|---|---|
| empty | ||
- window length
- —
- maxFreq
- 0
- to change
- —
- k
- 1
- best
- 0
- Inside the window
- Just added
- Window needs too many changes
- Just dropped
- Best window
We may change up to k = 1 letter. A window is fine if all of it can become ONE letter: keep the most common letter, replace the rest. "The rest" = window length − maxFreq, and that must be ≤ 1.
Which line is running?
function characterReplacement(s, k) {Running now: const count = new Map(); // letter -> how many times it is in the window let left = 0; let maxFreq = 0; // the highest count any one letter has reached let best = 0; for (let right = 0; right < s.length; right++) { count.set(s[right], (count.get(s[right]) ?? 0) + 1); maxFreq = Math.max(maxFreq, count.get(s[right])); // letters that are NOT the most common one must be replaced while (right - left + 1 - maxFreq > k) { count.set(s[left], count.get(s[left]) - 1); left++; } best = Math.max(best, right - left + 1); } return best;}Try k = 0: no changes allowed, so the window can only hold one kind of
letter, and the answer is the longest run that’s already there ("BBB", 3).
Step through the first example to the last letter. The window is "ABBA": 2 A’s
and 2 B’s. But maxFreq still says 3, from the earlier window "BABB". So
the code computes 4 − 3 = 1 change, when "ABBA" really needs 2. With
k = 1, "ABBA" is not a valid window, yet the while loop doesn’t shrink it.
Isn’t that wrong?
It’s out of date, but it never gives a wrong answer. Here’s why, slowly:
- Once a window of some length is valid,
bestremembers that length. We only care about finding a longer valid window. - A longer window means more letters, and with the same budget
k, it can only be valid if some letter appears more often than before:length ≤ maxFreq + k, so a biggerlengthneeds a biggermaxFreq. - So a window whose most common letter appears fewer than
maxFreqtimes can never beatbest. We don’t need its exact count. - While
maxFreqis out of date, the window just slides (one letter in, one letter out), keeping the same length. Some of these windows aren’t valid (like"ABBA"), but each is no longer thanbest, a length we already proved valid. Sobestdoesn’t change, and nothing wrong gets recorded. - The window can only grow again when a letter’s real, current count beats
maxFreq. At that moment the count is accurate, so the window really is valid.
That saves us from re-scanning all 26 counts every time a letter leaves. It also
means the while loop runs at most once per step (the window shrinks by one,
back to its old length), so you’ll often see this solution written with if.
Sliding window with counts
function characterReplacement(s, k) { const count = new Map(); // letter -> how many times it is in the window let left = 0; let maxFreq = 0; // the highest count any one letter has reached let best = 0; for (let right = 0; right < s.length; right++) { count.set(s[right], (count.get(s[right]) ?? 0) + 1); maxFreq = Math.max(maxFreq, count.get(s[right])); // letters that are NOT the most common one must be replaced while (right - left + 1 - maxFreq > k) { count.set(s[left], count.get(s[left]) - 1); left++; } best = Math.max(best, right - left + 1); } return best;}def character_replacement(s, k): count = {} # letter -> how many times it is in the window left = 0 max_freq = 0 # the highest count any one letter has reached best = 0 for right in range(len(s)): count[s[right]] = count.get(s[right], 0) + 1 max_freq = max(max_freq, count[s[right]]) # letters that are NOT the most common one must be replaced while (right - left + 1) - max_freq > k: count[s[left]] -= 1 left += 1 best = max(best, right - left + 1) return bestOn LeetCode it’s var characterReplacement = function(s, k) in JavaScript, and
def characterReplacement(self, s, k) inside class Solution in Python. Lines 1–12
match in both languages.
- Line 2:
countis a hash map from letter to how many times it’s in the window (Mapin JavaScript,dictin Python). - Lines 3–5:
leftis the window’s back edge;maxFreqis the highest count any letter has reached;bestis the answer so far. - Line 6:
right, the front edge, visits every index once. - Line 7: add the new letter to the counts.
count.get(x) ?? 0(JS) andcount.get(x, 0)(Python) mean “its count, or 0 if it’s not there yet”. - Line 8: the new letter is the only count that went up, so it’s the only one
that can beat
maxFreq. - Line 10: the validity check.
right − left + 1is the window’s length; minusmaxFreqis how many letters we’d have to change. More thank? Shrink. - Lines 11–12: the letter at the back leaves the window: lower its count and
move
leftforward. (We don’t touchmaxFreq; see above.) - Line 14 (JS) / line 13 (Python): the window is now no longer than one
we already know is valid, so
best = max(best, length)is safe. If the length is a new record, the window really is valid (itsmaxFreqis accurate then); otherwisebestjust stays the same. - Line 16 (JS) / line 14 (Python): return the best length.
s = "AABABBA", k = 1:
| right | letter | counts after adding | maxFreq | length − maxFreq | shrink? | window after | best |
|---|---|---|---|---|---|---|---|
| 0 | A | A:1 | 1 | 1 − 1 = 0 | no | A | 1 |
| 1 | A | A:2 | 2 | 2 − 2 = 0 | no | AA | 2 |
| 2 | B | A:2 B:1 | 2 | 3 − 2 = 1 | no | AAB | 3 |
| 3 | A | A:3 B:1 | 3 | 4 − 3 = 1 | no | AABA | 4 |
| 4 | B | A:3 B:2 | 3 | 5 − 3 = 2 | drop A | ABAB | 4 |
| 5 | B | A:2 B:3 | 3 | 5 − 3 = 2 | drop A | BABB | 4 |
| 6 | A | A:2 B:3 | 3 | 5 − 3 = 2 | drop B | ABBA | 4 |
The right = 3 row finds the answer, "AABA". From the right = 4 row on, the
window slides at length 4. In the right = 4 row the window "ABAB", and in the
right = 6 row the window "ABBA", have no letter 3 times, yet maxFreq is
still 3. Both really need 2 changes, so they aren’t valid, but they’re no longer
than best = 4: the out-of-date value from the section above, doing no harm.
Brute force
Time
O(n²)
About n × n ÷ 2 substrings, each extended by one letter in one step.
Space
O(1)
At most 26 letter counts, whatever the length.
Sliding window with counts
Time
O(n)
right moves n times and left moves at most n times in total, and each move updates one count. Double the string, double the work.
Space
O(1)
The count map never has more than 26 entries (one per capital letter).
What to say out loud:
- “For any window, the cheapest plan is to keep its most common letter. Changes needed = length − maxFreq.”
- “So a window is valid while length − maxFreq ≤ k. That’s a sliding window with letter counts.”
- “Grow on the right, shrink from the left when invalid. O(n) time, O(26) = O(1) space.”
- If asked, explain why
maxFreqnever needs to go down.
Likely follow-up questions:
- “Why is it fine that maxFreq is stale?” Use the five-step argument above: only a
higher
maxFreqcan produce a longer valid window. - “What if the string had any characters, not just A–Z?” Nothing changes except that the map can have more keys.
- “Max consecutive ones with k flips?” (Max Consecutive Ones III) The same window: count the zeros and keep that count ≤ k.
Related problems:
- Longest Substring Without Repeating Characters: the same window shape with a simpler rule.
- Permutation in String: window counts again, with a fixed window size.
- The window with counts pattern in the week overview.