Longest Repeating Character Replacement

Problem

You are given a string s of uppercase English letters and an integer k. You may change at most k characters of s to any other uppercase letters. Return the length of the longest substring consisting of a single repeated letter that you can produce this way.

Equivalently: find the longest window of s that can be made uniform by rewriting at most k of its characters.

Examples

• s = "ABAB", k = 2 → 4 — change both As (or both Bs) and the whole string becomes one letter.
• s = "AABABBA", k = 1 → 4 — change the middle B in "AABA" to get "AAAA" (window indices 0–3; "ABBA" → "BBBB" also works).
• s = "AAAA", k = 0 → 4 — already uniform; zero replacements needed.

Constraints

• 1 <= len(s) <= 10^5
• s contains only uppercase English letters (A–Z, so at most 26 distinct).
• 0 <= k <= len(s)

Checking all O(n²) windows is too slow at n = 10^5; the expected solution is O(n) (or O(26·n)).

Think about it first

TL;DR

Sliding window with letter counts, validity test window_len - max_freq <= k — O(26·n) time (O(n) with the never-shrink trick), O(26) = O(1) space.

Approach 1 — Brute force

Test every window: it’s fixable iff the characters other than its most frequent letter number at most k.

from collections import Counter

def characterReplacement(s: str, k: int) -> int:
    n = len(s)
    best = 0
    for i in range(n):
        counts: Counter[str] = Counter()
        for j in range(i, n):
            counts[s[j]] += 1
            window_len = j - i + 1
            if window_len - max(counts.values()) <= k:
                best = max(best, window_len)
    return best

Complexity: O(n²) time (each inner step is O(26)), O(1) space. At n = 10^5 that is roughly 10^10 character operations, too slow.

Approach 2 — Sliding window

A window is valid when window_len - max_freq <= k (replace everything that isn’t the majority letter). Validity is monotone: extending a window can only keep or break it, and shrinking can only keep or restore it. So as right moves forward, the smallest valid left for each right also only moves forward. Two pointers suffice, with no backtracking.

flowchart TD
    A[Extend right by one, increment count of s at right] --> B{window_len - max_freq > k?}
    B -->|Yes, invalid| C[Decrement count of s at left, advance left]
    C --> B
    B -->|No, valid| D[Update best with current window length]
    D --> A

from collections import Counter

def characterReplacement(s: str, k: int) -> int:
    counts: Counter[str] = Counter()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] += 1
        while (right - left + 1) - max(counts.values()) > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Walkthrough on s = "AABABBA", k = 1:

Answer: 4.

Complexity: max(counts.values()) scans at most 26 entries, so O(26·n) time; O(26) space. Each pointer moves at most n times total.

Approach 3 — Never-shrink window (stale max is safe)

Only the maximum window length matters, and max_freq only needs to be accurate when a new best is possible. If we let max_freq go stale (never recompute it after shrinking), the window can never grow past max_freq_ever + k, and that bound is achieved exactly by the true optimum. So replace the while with a single if that slides the window without shrinking, and drop the inner 26-scan.

from collections import Counter

def characterReplacement(s: str, k: int) -> int:
    counts: Counter[str] = Counter()
    left = 0
    max_freq = 0                       # highest single-letter count ever seen in a window
    for right, ch in enumerate(s):
        counts[ch] += 1
        max_freq = max(max_freq, counts[ch])
        if (right - left + 1) - max_freq > k:   # window one too big: slide, don't shrink
            counts[s[left]] -= 1
            left += 1
    return len(s) - left               # final window size = best size reached

Complexity: O(n) time, O(26) space. The window’s size never decreases, so its final size is the maximum valid size ever achieved.

Common pitfalls

• Recomputing max frequency after shrinking (or assuming you must). In Approach 2 the while + full max is correct but costs the 26 factor; in Approach 3 the stale max_freq is deliberately never decreased — decreasing it breaks the invariant.
• Validity formula direction: it’s window_len - max_freq <= k (replace the minority), not max_freq <= k.
• Recording best inside the shrink loop. Record only after the window is valid again, or you’ll count an invalid window.
• k = 0 still works — the algorithm degenerates to “longest run of one letter”; don’t special-case it.

Pattern takeaway

The variable-size window: maintain a cheap summary (letter counts) whose validity predicate is monotone in window extension, grow right unconditionally, shrink left only while invalid, and record sizes when valid. The refinement worth remembering: when only the maximum window size is asked for, you can slide instead of shrink, so the window never gives back length it has reached.