Big O Practice: Longest Repeating Char Replacement

def character_replacement(s, k):
    counts = {}
    left = 0
    max_count = 0
    best = 0
    for right, c in enumerate(s):
        counts[c] = counts.get(c, 0) + 1
        max_count = max(max_count, counts[c])
        while right - left + 1 - max_count > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Variables

• n - length of the input string

Explanation

The window shifts forward only - each index enters and leaves at most once, giving **O(n)** time despite the inner while-loop. The counts map holds at most one entry per alphabet character, so space is **O(1)** for a fixed alphabet. The subtle part: `max_count` is never decremented, but the overall answer remains correct because the window size only matters at its peak.

More Big O practice problems · Today's daily problem