Longest Repeating Character Replacement

Longest Repeating Character Replacement is a classic sliding window problem with a clever twist: the window grows freely and only shrinks when it becomes too expensive to fix.

The slow way first

The obvious idea: try every substring, and for each one count its most frequent character. A substring of length len works if len - maxFreq <= k, because every other character can be swapped to match the most common one. Checking all substrings is O(n²) (or worse), which is too slow for large strings.

The question to ask: as I extend a window to the right, can I avoid re-scanning it every time? Yes — if I keep a running count of characters inside the window, I can decide validity in O(1).

The idea: grow, and only shrink when invalid

Keep a window [L, R] and a count of how often each character appears inside it. Let maxFreq be the highest of those counts. The number of characters we would have to replace is (R - L + 1) - maxFreq.

• If that is <= k, the window is valid — record its length.
• If it exceeds k, the window is invalid — slide L right (dropping a character) until it is valid again.

The neat part: len - maxFreq is exactly how many characters are not the majority char — and those are precisely the ones we would replace.

Walk through it

Step through the animation. R marches right, adding each character to the count. As long as the window can be fixed with 1 swap it keeps growing, reaching length 4 on "AABA". When adding a fifth character pushes the needed swaps to 2 > k, the L pointer slides right to drop a character and restore validity. The best length ever seen — 4 — is the answer.

Pseudocode

count = empty map
L = 0, best = 0, max_freq = 0
for R from 0 to len(s) - 1:
    count[s[R]] += 1
    max_freq = max(max_freq, count[s[R]])
    while (R - L + 1) - max_freq > k:   # window needs too many swaps
        count[s[L]] -= 1                # drop the leftmost char
        L += 1
    best = max(best, R - L + 1)         # this window is valid
return best

The Python solution

def character_replacement(s, k):
    from collections import Counter
    count = Counter()
    L = best = max_freq = 0
    for R in range(len(s)):
        count[s[R]] += 1
        max_freq = max(max_freq, count[s[R]])
        while (R - L + 1) - max_freq > k:
            count[s[L]] -= 1
            L += 1
        best = max(best, R - L + 1)
    return best

• count tracks how many of each character are inside the current window.
• max_freq is the count of the window's most common character — the one we keep, replacing all others.
• (R - L + 1) - max_freq is the number of replacements the window needs. If it exceeds k, the while loop shrinks from the left.
• best records the longest valid window length we have seen.
• Subtle but fine: max_freq is never decreased when we shrink. That can leave it slightly stale, but it can only under-count future windows, so best is never overstated — and the answer stays correct.

Complexity

L and R each move forward at most n times, so the whole scan is O(n). The count map holds at most 26 uppercase letters, so the extra space is O(1).

When this pattern shows up

Practice