Editorial: Longest Repeating Character Replacement

by admin · Oct. 18, 2026

1 Intuition

A window is fixable when (window length − count of its most common letter) ≤ k.

2 Approach

Slide a window, tracking letter counts and the highest count seen; shrink when the window needs more than k changes.

3 Complexity Analysis

Time O(n), Space O(1) for 26 letters.

4 Solution Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count, lo, top, best = {}, 0, 0, 0
        for hi, c in enumerate(s):
            count[c] = count.get(c, 0) + 1
            top = max(top, count[c])
            while hi - lo + 1 - top > k:
                count[s[lo]] -= 1
                lo += 1
            best = max(best, hi - lo + 1)
        return best

5 Code Walkthrough

The reference solution below implements the approach step by step.