Longest Repeating Character Replacement

Test every window

For each left edge, extend a right edge and count the 26 letters. A window of length window_length needs window_length - max_frequency replacements: keep its most frequent letter and change the rest.

def character_replacement(s: str, k: int) -> int:
    best = 0
 
    for left in range(len(s)):
        counts = [0] * 26
        for right in range(left, len(s)):
            index = ord(s[right]) - ord("A")
            counts[index] += 1
            max_frequency = max(counts)
            window_length = right - left + 1
            if window_length - max_frequency <= k:
                best = max(best, window_length)
 
    return best

Scanning all 26 buckets for every candidate makes the cost explicit. Time O(n² · 26), Space O(26).

Majority window

The brute force rebuilds nearly the same windows. Keep one sliding window — a contiguous range whose edges move during the scan — and store its 26 letter counts.

As right grows, update max_count, the largest single-letter count reached while the window grows. If window_length - max_count > k, move left and remove that letter from the counts.

def character_replacement(s: str, k: int) -> int:
    counts = [0] * 26
    left = 0
    max_count = 0
    best = 0
 
    for right, char in enumerate(s):
        index = ord(char) - ord("A")
        counts[index] += 1
        max_count = max(max_count, counts[index])
 
        while right - left + 1 - max_count > k:
            left_index = ord(s[left]) - ord("A")
            counts[left_index] -= 1
            left += 1
 
        best = max(best, right - left + 1)
 
    return best

max_count may become stale after left moves, and that's deliberate. It records the majority count that already supported a valid window of this size. A stale value can keep the current window wide, but the answer grows only when a new character supports a genuinely larger size.

Each edge moves only forward. Time O(n), Space O(26).