Longest Repeating Character Replacement

You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Either replace the 'X's with 'Y's, or replace the 'Y's with 'X's.

Approach

Use a sliding window with a 26-length count array and track the maximum frequency of any character in the window. The window is valid if window_size - max_count <= k (the number of replacements needed). Expand right, and if it becomes invalid, shrink from the left. Track the largest valid window length.

Why It Works

The best way to make all characters in a window the same is to keep the most frequent character and replace the rest. Therefore, a window is feasible exactly when the number of non-max characters is at most k. Sliding the window maintains this invariant and explores all candidates.

Complexity

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

Reference Implementation (Python)

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = [0] * 26
        left = 0
        max_count = 0
        best = 0

        for right, ch in enumerate(s):
            idx = ord(ch) - ord('A')
            counts[idx] += 1
            if counts[idx] > max_count:
                max_count = counts[idx]

            while (right - left + 1) - max_count > k:
                counts[ord(s[left]) - ord('A')] -= 1
                left += 1

            best = max(best, right - left + 1)
        return best