STEP 10 · SLIDING WINDOW · SLIDING WINDOW · MEDIUM

Longest Repeating Character Replacement

WHAT IT SAYS

Given a string and a budget k, find the longest stretch you can turn into a single repeated character by replacing at most k characters.

WHAT IT'S REALLY ASKING

"You are not choosing which letter to keep — the stretch already tells you (keep whichever letter is most common inside it, and pay for the rest). So a stretch has one number attached to it: width minus its majority count. Everything past that is: which stretches can you afford, and can an unaffordable stretch ever become affordable by growing?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Every substring, every target letter

O(n² · 26) time, O(26) space

For each start i, extend right, keep a frequency table of the window, and for each of the 26 possible target letters ask whether the window can be converted for k replacements or fewer. Take the longest window that any letter can pay for. Nothing is missed, so it's correct.

WHERE THE WORK IS WASTED — Two separate redundancies stacked on top of each other. First, the 26-way loop is decided before you run it: for a fixed window, keeping letter c costs width − freq[c], and that's smallest for the c with the biggest freq — you scan all 26 to rediscover the maximum you could have tracked as you went. Second, restarting at i + 1 rebuilds a frequency table that differs from the one you just finished by a single character, and then busts on the very same character that busted the previous start.

KEY OBSERVATION — THE UNLOCKlink

You never pick the letter. The majority picks itself.

Fix a window. If you commit to making everything letter c, you must replace every character that isn't c, so the price is exactly width − freq[c]. You want the cheapest commitment, so you want the c that maximises freq[c] — the most frequent character already inside. No tie-breaking, no case analysis, no lookahead: the majority letter is optimal for that window, always, because any other choice replaces strictly more characters. So 26 questions collapse into one number. A window is affordable exactly when width − maxFreq ≤ k. The target letter has stopped being a decision and become a byproduct — you're now just hunting for the widest window whose non-majority residue fits in the budget.

KEY OBSERVATION — THE UNLOCKlink

Growing right never gets cheaper. Trimming left never gets dearer.

Add one character to the right: width goes up by 1, and maxFreq goes up by either 1 (you extended the current majority) or 0. So the cost width − maxFreq either stays put or rises by 1 — it can never fall. Which means a window that has already blown the budget is dead, and it stays dead no matter how much further right you push. Every start at or before it is dead with it. Run the same argument backwards: drop a character off the left and width falls by 1 while maxFreq falls by at most 1, so cost never increases. Affordability is hereditary — if [l..r+1] fits the budget, so did [l..r]. Therefore the leftmost affordable start for r+1 is never to the left of the leftmost affordable start for r. The left edge is monotone: it advances or it waits, but it never rewinds.

Right pays, left evicts, majority is just a counter

O(n) time, O(26) space

Walk the right edge forward, incrementing that character's count and refreshing maxFreq (the new character is the only one that could have become the majority, so it's an O(1) check). While width − maxFreq exceeds k, advance the left edge and decrement its count. Every index enters and leaves at most once, and the widest window you ever legally hold is the answer.

The stale-majority trick

O(n) time, O(26) space, one pointer move per index

Since only the maximum width matters, an over-budget window never has to shrink — it only has to stop growing. Replace the while with a single if, sliding left by exactly one so the width is preserved, and stop recomputing maxFreq downward: let it stay as the best majority count ever seen. A stale, too-large maxFreq can only make the window look cheaper than it is, and the window will only widen again once a genuinely affordable window of the next width appears — so the final width is the answer, no max() bookkeeping needed.

WHAT YOU TRADED — The speedup costs you nothing but generality, and the price is hidden in the word 'majority': the whole thing works because the best target letter is a function of the window alone, and because cost is monotone in width. Break either — make the replacement cost depend on which letter you're replacing, say — and the majority stops being self-evident, the left edge is free to rewind, and you're back to inspecting windows one at a time.

WATCH THE IDEA RUN

width 0

majority '-' 0

best 0

price / 1 0

Budget: 1 replacement. You never choose a target letter — watch the window hand you one.

step 1 / 19

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Self-Selecting Majority Window

YOU'LL SEE IT AGAIN WHEN

The problem seems to ask you to commit to a choice (which letter, which value, which colour) before you can evaluate a window — but the window's own contents make that choice for you.
You want the longest contiguous stretch under a budget, and the cost of a stretch only rises as it widens and only falls as it narrows.
The cost of a window is computable in O(1) from a small tally that updates as one element enters or leaves.
Brute force would loop over all possible targets inside the loop over all windows — a nested search where the inner answer is forced by the outer state.

SAME BLUEPRINT, DIFFERENT PROBLEM

Max Consecutive Ones IIIFruit Into BasketsLongest Substring with At Most K Distinct CharactersMinimum Window Substring

The bar isn't "solved it once." It's "could rebuild it from the observation."