#424MediumSliding window

Longest Repeating Character Replacement

The tell: Longest window that becomes uniform after at most k changes.

How you get there

1A window is valid when (length − count of its most frequent character) ≤ k.
2That difference is exactly how many characters must be replaced.
3Shrink from the left whenever the window becomes invalid.

Solution

Python

from collections import defaultdict

def character_replacement(s: str, k: int) -> int:
    counts: dict[str, int] = defaultdict(int)
    start = best = max_count = 0

    for i, ch in enumerate(s):
        counts[ch] += 1
        max_count = max(max_count, counts[ch])
        while (i - start + 1) - max_count > k:
            counts[s[start]] -= 1
            start += 1
        best = max(best, i - start + 1)
    return best

Time: O(n)
Space: O(alphabet)

What goes wrong

Recomputing max(counts.values()) inside the loop is correct but turns an O(n) solution into O(n · alphabet).

Test yourself on DSA Next: Permutation in String →