Longest Repeating Character Replacement

PracticeNeetCode ↗LeetCode ↗

Given a string s of uppercase letters and an integer k, you may replace up to k characters in the string with any other uppercase letter. Return the length of the longest substring containing a single repeating character you can achieve after at most k replacements.

Example

Key Pointers

• A window is achievable if (window length) - (count of its most frequent character) <= k — that difference is exactly how many characters would need replacing.
• Track the max character frequency seen inside the current window; it never needs to decrease as the window grows, since a stale high value only makes the window look more achievable, never less.
• When a window becomes unachievable, shrink from the left by exactly one instead of recomputing from scratch — the best answer only ever grows or holds steady, never truly shrinks.

Step-by-Step Analysis

1. Initialize left = 0, a character count map, max_freq = 0, and result = 0.
2. For each index right: increment the count for s[right], then update max_freq.
3. While (right - left + 1) - max_freq > k: decrement the count for s[left] and move left forward.
4. Update result with the current window size.
5. Return result.

Complexity

Time: O(n) — Space: O(1) (26 letters)

Code

def characterReplacement(s: str, k: int) -> int:
    count = {}
    left = 0
    max_freq = 0
    result = 0
    for right in range(len(s)):
        ch = s[right]
        count[ch] = count.get(ch, 0) + 1
        max_freq = max(max_freq, count[ch])
        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1
        result = max(result, right - left + 1)
    return result

Code Explanation

How the solution above works, piece by piece.

1. The window is valid when window length − max_freq ≤ k: keep the most common letter and replace everything else, which takes that many edits.
2. Add s[right] to count and update max_freq.
3. While the window needs more than k replacements, drop s[left] and move left right.
4. result tracks the biggest valid window.
5. max_freq is never decreased when shrinking. That's safe: the answer can only improve when a higher frequency appears, so a stale value never produces a wrong result. O(n) time, O(26) space.

Visual Walkthrough

Running it on s = "AABABBA", k = 1:

Video Explanation

NeetCode — LeetCode 424