Longest Repeating Character Replacement Solution

Problem

Given a string of uppercase English letters and an integer k, find the length of the longest substring you can turn into a single repeating character by changing at most k of its characters to anything you like.

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace one 'B' in "AABA" (indices 0–3) to get "AAAA", which has length 4.

Counter-example: s = "ABCDE", k = 1 → output 2 — any three-character window has at least two distinct characters requiring two replacements, which exceeds k=1.

Intuition

A window can be turned into a single repeating character if and only if the number of non-majority characters is at most k — that is, window_size - max_frequency ≤ k. To maximize the window, we only care about making it larger than the best we've seen, so max_count (the highest character frequency encountered so far) never needs to decrease: a smaller max would only shrink the valid window, which is never useful.

Approach 1 — Brute Force

Try every pair of indices as window boundaries, maintaining a frequency array as the right pointer extends, and check the replacement condition at each step.

For each starting index left, reset a fresh frequency array and max_count.
Extend right one step at a time, incrementing the new character's frequency.
Update max_count with the new character's frequency.
If (right - left + 1) - max_count <= k, the window is valid — update the result.
Repeat until right reaches the end, then advance left.

1def characterReplacement(s: str, k: int) -> int:
2    result = 0
3    for left in range(len(s)):
4        char_count = [0] * 26
5        max_count = 0
6        for right in range(left, len(s)):
7            char_count[ord(s[right]) - ord('A')] += 1
8            max_count = max(max_count, char_count[ord(s[right]) - ord('A')])
9            if (right - left + 1) - max_count <= k:
10                result = max(result, right - left + 1)
11    return result

Time: O(n²) — all pairs of window boundaries, each O(1) step thanks to the incremental frequency update
Space: O(1) — fixed 26-element frequency array regardless of input length

Approach 2 — Sliding Window

Maintain a window that only grows or shifts — it never truly shrinks. max_count is kept at its historical peak because we only care about finding a window longer than the current best; a lower max would just mean a smaller valid window, which is useless.

Track a 26-element frequency array and max_count — the highest character frequency seen in any valid window so far.
Extend right one step at a time, incrementing the new character's frequency.
Update max_count with the new character's frequency.
If (window_size - max_count) > k, the window needs too many replacements — shift left forward by one and decrement that character's count. Use if, not while: shifting more than once would shrink the window below its previous maximum, which is never beneficial.
After the loop, the window size is len(s) - left.

1def characterReplacement(s: str, k: int) -> int:
2    char_count = [0] * 26
3    max_count = 0  # highest frequency seen in any valid window; intentionally never decremented
4    left = 0
5
6    for right in range(len(s)):
7        char_count[ord(s[right]) - ord('A')] += 1
8        max_count = max(max_count, char_count[ord(s[right]) - ord('A')])
9
10        # shift window by one without shrinking when replacements exceed budget
11        if (right - left + 1) - max_count > k:
12            char_count[ord(s[left]) - ord('A')] -= 1
13            left += 1
14
15    return len(s) - left

Time: O(n) — each character is touched at most twice as right and left each traverse the string once
Space: O(1) — fixed 26-element frequency array

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Verifying correctness on small inputs; establishing the core condition in an interview explanation
Sliding Window	O(n)	O(1)	Always — linear time with no extra space is the canonical solution

Common Mistakes

Decrementing max_count when shifting the left pointer — max_count must stay at its peak across all windows seen so far; lowering it would allow a smaller valid window to pass as if it were an improvement, corrupting the result.
Using while instead of if to shrink the window — repeatedly shrinking until the window is valid again is correct logically, but it allows the window to become smaller than the best seen, costing O(n) extra work per step and eliminating the O(n) guarantee.
Returning right - left + 1 inside the loop — the final window after the last iteration is the answer; read len(s) - left (or right - left + 1 at the end of the loop body) rather than tracking a separate result variable, or track result by updating it inside the loop before the shift check.
Assuming replacements must be contiguous — the k replacements can be spread anywhere in the window; "ABBA" with k=2 → "AAAA" is valid even though the two A's aren't adjacent, because we're replacing both B's independently.
Using a hash map instead of a fixed array — the problem guarantees uppercase English letters only, so a 26-element array indexed by char - 'A' is both simpler and faster than a dictionary.

Longest Repeating Character Replacement — Solution