Q25: Longest Repeating Character Replacement. - DSA Patterns (Multi-Lang)

In Simple Words: Sliding window where window is valid if windowSize - maxFreq <= k (meaning non-majority characters can all be replaced). If invalid, shrink left pointer.

Time: $O(N)$ | Space: $O(26) = O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def characterReplacement(s: str, k: int) -> int:
    counts = {}
    max_f = 0
    l = 0
    res = 0
    for r in range(len(s)):
        counts[s[r]] = counts.get(s[r], 0) + 1
        max_f = max(max_f, counts[s[r]])
        while (r - l + 1) - max_f > k:
            counts[s[l]] -= 1
            l += 1
        res = max(res, r - l + 1)
    return res