Longest Repeating Character Replacement

mediumTests passed 2026-11-11v1.0.0

TC: O(N)|SC: O(1)

Sliding Window Original Statement (leetcode).md

1. Core Invariant / The Trick

A window `[l..r]` is valid iff `windowLength - maxFreq <= k`. Crucial optimization: never shrink `maxFreq` down when advancing `l`, because a strictly longer window requires a strictly larger `maxFreq`!

2. Complexity Bounds & Proof

Eliminates inner O(26) max recalculation; `l` advances at most once per `r` step.

3. Minimal Idiomatic Code

def characterReplacement(s: str, k: int) -> int:
    cnt = {}
    l = max_f = best = 0
    for r, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1
        max_f = max(max_f, cnt[c])
        while (r - l + 1) - max_f > k:
            cnt[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

4. Failure Modes & Interview Follow-ups

Pitfalls:- Thinking `maxFreq` becomes stale breaks correctness—monotonic window size only improves when `maxFreq` strictly rises.

Follow-ups:- Longest Subarray of 1s after flipping at most K zeros is identical with binary domain.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Longest Substring Without Repeating Characters (O(N))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.