Longest Repeating Character Replacement

The brute force checks every substring and counts how many characters would need to change. The optimal approach reframes the question: a window of length L is achievable if L - (count of its most frequent character) <= k, since that difference is exactly how many characters need replacing. So we grow a sliding window, track the highest character frequency seen inside it, and only shrink when the window can no longer be fixed with k replacements.

Brute Force

Time O(n² · 26)Space O(1)

For every window [i, j], count character frequencies and check if (j - i + 1) - max_frequency <= k.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        best = 0
        for i in range(n):
            count = {}
            max_freq = 0
            for j in range(i, n):
                count[s[j]] = count.get(s[j], 0) + 1
                max_freq = max(max_freq, count[s[j]])
                if (j - i + 1) - max_freq <= k:
                    best = max(best, j - i + 1)
        return best

Why it’s slow: there are O(n²) windows, and recomputing the character counts and max frequency for each one (even incrementally) still means O(n) windows per starting index — O(n²) total, with an extra constant factor for tracking frequencies of up to 26 letters.

Sliding Window (Max Frequency Tracking)

OptimalTime O(n)Space O(1)

Expand right one character at a time, incrementing its count and updating max_freq, the highest frequency of any single character seen so far inside the window. If the window size minus max_freq exceeds k — meaning even replacing every non-majority character would not be enough — shrink from left by one. Note that max_freq is never decreased on shrink: it only ever needs to be a valid historical bound to prove a window of that size was once achievable, so this does not affect correctness, only simplifies the code.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        left = 0
        max_freq = 0
        best = 0
        for right, ch in enumerate(s):
            count[ch] = count.get(ch, 0) + 1
            max_freq = max(max_freq, count[ch])
            window_len = right - left + 1
            if window_len - max_freq > k:
                count[s[left]] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Watch how the window grows while max_freq climbs, and why max_freq may stay pinned above the window’s real peak even after a shrink — that historical bound is what keeps the answer correct.

Window [left 0, right 0] = “A”

ALR

Letter counts in window

A x1B x0

the bar matching maxFreq is the window's true peak

size

maxFreq

need size - maxFreq

valid

1 / 10

currentseenresultdiscarded

`A` joins: window is a single char, size 1, maxFreq 1, need 0, and 0 is at most k. A one-char window is already uniform, so best = 1.

Correctness: the check window_len - max_freq <= k is exactly the condition that the window can be made all one character using at most k replacements — replace every character that is not the most frequent one. Using a historical max_freq never over-counts what is achievable (it is a true frequency that existed), so it never accepts an invalid window; it also never causes us to miss the true best, since the window only ever shrinks by exactly one when it becomes invalid, keeping every valid window length considered.

Complexity: right visits each index once and left moves at most n times total — O(n) time. The count map holds at most 26 uppercase letters — O(1) space.

Longest Repeating Character Replacement

Brute Force

Sliding Window (Max Frequency Tracking)

More Sliding Window practice