Longest Repeating Character Replacement and the Lazy Window

This one is a Medium-rated classic reported from Google, Uber, Amazon interviews: "Longest Repeating Character Replacement". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Sliding Window pattern on sight. Part 4 of 11 in the Sliding Window arc.

The Problem

Given a string s of uppercase letters and an integer k, you may replace at most k characters so that the longest run of identical characters is as long as possible. Return that length. The window condition — window size minus the count of its most frequent character being at most k — is the crux.

Input:  s = "AABABBA", k = 1
Output: 4
Replace the middle "A" to get "AABBBBA" — the run "BBBB" has length 4.

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Longest window where (window length − max frequency) ≤ k is a constraint window, but with a twist: the answer only improves when max frequency improves, so the window never needs to shrink below its best size — it can slide without contracting.

The Approach

Track letter counts and the best max-frequency seen. Grow right; if the window becomes invalid, move left forward once rather than looping — the window slides at its current best size instead of shrinking. The final window size is the answer.

Using a stale best_freq is deliberately safe: an oversized window is only recorded when a genuinely higher frequency re-validates it. Explaining why the laziness is correct is what this question actually tests.

Python Solution

def character_replacement(s: str, k: int) -> int:
    """Longest run achievable with at most k replacements."""
    counts: dict[str, int] = {}
    left = 0
    best_freq = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        best_freq = max(best_freq, counts[ch])
        if (right - left + 1) - best_freq > k:
            counts[s[left]] -= 1   # slide, do not shrink
            left += 1
    return len(s) - left

Complexity

• Time: O(n) — right advances n times; left advances at most n times
• Space: O(1) — counts over a 26-letter alphabet

Interview Tips and Follow-Ups

• Be ready to defend the stale best_freq — most candidates cannot, and it is the first thing a strong interviewer pokes.
• The honest-shrinking version (while-loop, recompute validity) is also accepted; know both and say why the lazy one still returns the max.
• Sibling problem: Max Consecutive Ones III is this exact question with a binary alphabet — it appears later in this arc.

That wraps part 4 of the Sliding Window arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.