Skip to content
16-Week DSA Roadmap
LeetCode #424MediumProblem 7 of 8

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)

The problem in plain English

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.

s
  1. A0
  2. A1
  3. B2
  4. A3
  5. B4
  6. B5
  7. A6
Take 'AABA' (indexes 0 to 3) and change its one B into an A: 'AAAA', a run of 4. That's the best possible with one change.

The rules that matter:

  • A “run” is a substring: letters that sit next to each other.
  • You can make at most k changes (fewer is fine). k can be 0.
  • Only capital letters A to Z.

Before you code: think it through

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

window length 4 = keep 3 + change 1

change 1 ≤ k = 1: valid

'AABA' has length 4. The 3 A's are kept (green), the 1 B must change (amber). 1 change ≤ k = 1, so this stretch is allowed.

Pause and think

With k = 1, is 'AABAB' (length 5) allowed? What about 'BABB'?

Approach 1: Brute force

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

s
  1. A0
  2. B1
  3. A2
  4. B3
count0 items
letterin window
empty
variables
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?

Step 1 / 12

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 best

Why is it slow?

A 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.

The pattern: window with counts and a validity check

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

Template

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”

Approach 2: Sliding window with counts

  1. Start with an empty count map, left = 0, maxFreq = 0, best = 0.
  2. Move right from the first letter to the last. Add s[right] to the counts.
  3. Update maxFreq if this letter’s count is now the highest we’ve seen.
  4. While (right − left + 1) − maxFreq > k, the window needs too many changes: lower the count of s[left] and move left right.
  5. 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 best if 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

s
  1. A0
  2. A1
  3. B2
  4. A3
  5. B4
  6. B5
  7. A6
count0 items
letterin window
empty
variables
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.

Step 1 / 22

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).

Why we never lower maxFreq

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:

  1. Once a window of some length is valid, best remembers that length. We only care about finding a longer valid window.
  2. 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 bigger length needs a bigger maxFreq.
  3. So a window whose most common letter appears fewer than maxFreq times can never beat best. We don’t need its exact count.
  4. While maxFreq is 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 than best, a length we already proved valid. So best doesn’t change, and nothing wrong gets recorded.
  5. 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.

The code, line by line

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 best

On 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: count is a hash map from letter to how many times it’s in the window (Map in JavaScript, dict in Python).
  • Lines 3–5: left is the window’s back edge; maxFreq is the highest count any letter has reached; best is 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) and count.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 + 1 is the window’s length; minus maxFreq is how many letters we’d have to change. More than k? Shrink.
  • Lines 11–12: the letter at the back leaves the window: lower its count and move left forward. (We don’t touch maxFreq; 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 (its maxFreq is accurate then); otherwise best just stays the same.
  • Line 16 (JS) / line 14 (Python): return the best length.

Dry run

s = "AABABBA", k = 1:

rightlettercounts after addingmaxFreqlength − maxFreqshrink?window afterbest
0AA:111 − 1 = 0noA1
1AA:222 − 2 = 0noAA2
2BA:2 B:123 − 2 = 1noAAB3
3AA:3 B:134 − 3 = 1noAABA4
4BA:3 B:235 − 3 = 2drop AABAB4
5BA:2 B:335 − 3 = 2drop ABABB4
6AA:2 B:335 − 3 = 2drop BABBA4
s = "AABABBA", k = 1

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.

Complexity

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).

Common mistakes and edge cases

What to say out loud:

  1. “For any window, the cheapest plan is to keep its most common letter. Changes needed = length − maxFreq.”
  2. “So a window is valid while length − maxFreq ≤ k. That’s a sliding window with letter counts.”
  3. “Grow on the right, shrink from the left when invalid. O(n) time, O(26) = O(1) space.”
  4. If asked, explain why maxFreq never 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 maxFreq can 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: