Longest Repeating Character Replacement

Find the longest substring that can be turned into all one letter using at most k replacements.

Before you code

Decide what makes a window feasible: a window works when its length minus its most frequent letter count is at most k, because those other letters are exactly the ones you would replace.

Hints

1. Grow the right end and count letters; shrink the left end whenever window_length - max_count passes k.
2. Track the max frequency in the window — the classic linear version keeps a stale high value and stays correct, because only the best length is ever recorded.
3. Record the best length after every step, and never move the left end backward.

Production & complexity notes

When solving Longest Repeating Character Replacement on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Sliding window to reinforce the underlying pattern.

What it practices

A sliding window with a feasibility rule, from Sliding window.