Longest Repeating Character Replacement

Intuition

For any window, the cheapest way to make it uniform is to keep its most frequent letter and rewrite the rest, which costs (window length minus that top frequency) changes. A window is affordable when that cost is at most k. Expanding the right edge and only nudging the left edge forward when the cost exceeds k keeps the window at the largest width achieved so far, so the best length never needs to be recomputed by shrinking eagerly.

Algorithm walkthrough

1. 1Track counts of each letter in the current window and the highest single-letter frequency seen.
2. 2Advance the right edge, updating the count and the running maximum frequency.
3. 3If window length minus the max frequency exceeds k, move the left edge forward and decrement its count.
4. 4Update the best length with the current window width after each step.
5. 5Return the best width once the whole string has been processed.

Implementation

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0] * 26
        left = 0
        max_freq = 0
        best = 0
        base = ord('A')
        for right, ch in enumerate(s):
            idx = ord(ch) - base
            count[idx] += 1
            max_freq = max(max_freq, count[idx])
            while (right - left + 1) - max_freq > k:
                count[ord(s[left]) - base] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best