Longest Repeating Character Replacement

1. Define the problem

Longest Repeating Character Replacement

Given a string s and an integer k, return the length of the longest substring you can make all the same letter with at most k replacements . A window is valid when length minus the count of its majority character is at most k; shrink left when that budget is exceeded.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only uppercase English letters
0 ≤ k ≤ s.length

Example

Inputs = "AABABBA", k = 1

Output4

Explanation Replace one B in "AABA" or one A in "ABBA" to get a run of 4.

2. Visualize the solution

Keep replacements within k

Statusvalid

Window "AAB": majority A=2, replacements 1 <= k; best = 3.

What happens in this step

window = [0, 2]  ("AAB")

before: counts = {A:2}, maxCount = 2 (from right = 1)
  add s[2] = 'B' → counts = {A:2, B:1}, maxCount stays 2

window length 3, replacements needed = 3 − 2 = 1 ≤ k(1) — valid; best becomes 3.

Step 1 of 5

Steps to visualize

Grow right and bump the count of the entering character.
Track the majority count in the window (most frequent letter).
Replacements needed equal window length minus majority count.
When that exceeds k, shrink left and drop the leaving character.
Track the longest window that stays within the replacement budget.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Keep replacements within k

Statusvalid

Window "AAB": majority A=2, replacements 1 <= k; best = 3.

What happens in this step

window = [0, 2]  ("AAB")

before: counts = {A:2}, maxCount = 2 (from right = 1)
  add s[2] = 'B' → counts = {A:2, B:1}, maxCount stays 2

window length 3, replacements needed = 3 − 2 = 1 ≤ k(1) — valid; best becomes 3.

Step 1 of 5

4. Solution

Solution

solution.tsTypeScript

function characterReplacement(s, k) {
  const counts = new Map();
  let left = 0;
  let maxCount = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    counts.set(c, (counts.get(c) ?? 0) + 1);
    maxCount = Math.max(maxCount, counts.get(c));

    const windowLen = right - left + 1;
    if (windowLen - maxCount > k) {
      const leftChar = s[left];
      counts.set(leftChar, counts.get(leftChar) - 1);
      left++;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

Time: O(n)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`s = "AABABBA", k = 1`	`4`	Docstring example
`s = "A", k = 0`	`1`	Single character
`s = "AAAA", k = 2`	`4`	Entire string already one character
`s = "ABCDE", k = 0`	`1`	k = 0 with no repeats
`s = "BBBB", k = 0`	`4`	All identical elements
`s = "ABCD", k = 3`	`4`	k covers the whole string
`s = "ABAB", k = 2`	`4`	Replace both B's with A
`s = "AABABBA", k = 0`	`2`	Classic second example with k = 0

Longest Repeating Character Replacement