Longest Repeating Character Replacement

Solving tips

Key validity test: a window is fixable when window_len - count_of_most_frequent_letter <= k, so you only replace the non-majority characters.
Since validity is monotone, use a variable-size window: grow right unconditionally, shrink left while invalid, and record the max size.
Optimization: track a stale max_freq that never decreases and slide (if not while), giving true O(n) instead of O(26*n) and never shrinking the window.
Common pitfall: the formula is window_len - max_freq <= k (not max_freq <= k), and record best only when the window is valid.

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

Hint 1

For a fixed window, which characters should you replace? Everything except the most frequent letter. The window is fixable iff window_length - count_of_most_frequent_letter <= k.

Hint 2

As the window grows rightward it can only get harder to fix, and shrinking from the left can only help. That monotonicity means two pointers that never move backward suffice.

Hint 3

Keep letter counts in the window. Extend right each step; while (right - left + 1) - max(counts) > k, decrement counts at s[left] and advance left. The answer is the largest valid window seen. (Bonus: you never need to shrink below the best size — a stale max frequency still yields the right answer.)

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

class Solution:
    def characterReplacement(self, 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’s ~10^10 character operations — dead on arrival.

Approach 2 — Sliding window

The insight: 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 validity, and shrinking can only keep or restore it. So as right sweeps forward, the smallest valid left for each right only moves forward — two pointers, no backtracking.

from collections import Counter

class Solution:
    def characterReplacement(self, 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:

right	ch	window	len - max_freq	action	best
0	A	`A`	1-1=0 ✓	—	1
1	A	`AA`	2-2=0 ✓	—	2
2	B	`AAB`	3-2=1 ✓	—	3
3	A	`AABA`	4-3=1 ✓	—	4
4	B	`AABAB`	5-3=2 ✗	shrink → `ABAB` (4-2=2 ✗) → `BAB` (3-2=1 ✓)	4
5	B	`BABB`	4-3=1 ✓	—	4
6	A	`BABBA`	5-3=2 ✗	shrink → `ABBA` (4-2=2 ✗) → `BBA` (3-2=1 ✓)	4

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)

The insight: we only care about the maximum window length, and the tracked max_freq only needs to be right 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 rigidly, and drop the inner 26-scan.

from collections import Counter

class Solution:
    def characterReplacement(self, 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 workhorse 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 may slide rather than shrink — the window as a ratchet that never gives back length it has earned.