Longest Repeating Character Replacement: The Sliding Window Budget Check

Longest Repeating Character Replacement is where the sliding window pattern stops being mechanical. Easier window problems ask "does the window contain X?" — a yes/no membership check. This one asks something sneakier: could this window be fixed if you were allowed k edits? The answer requires a frequency count and one line of arithmetic.

The twist that unlocks the whole problem: you never actually replace a single character. No mutation, no trying combinations. You just measure how far each window is from being uniform, and keep the window as large as possible while at most k characters differ from the most frequent letter inside it.

The problem#

Given an uppercase string s and an integer k, you may replace at most k characters with any other uppercase letter. Return the length of the longest substring that can be made into a run of one repeated character.

Two constraints shape everything downstream:

• k is a replacement budget, not a limit on distinct characters. A window with five different letters is fine if fixing it needs at most k flips.
• The answer is a length, not the substring or the edited string — so you never need to know which characters to flip, only how many flips a window would need.

The brute force baseline#

Check every substring: for each start index, extend the end one character at a time, keep frequency counts, and test whether the substring can be made uniform within budget.

This already contains the core validity test (more on it below), but it evaluates all O(n²) substrings. At n = 10⁵ that's on the order of ten billion window checks. The wasted work is obvious once you see it: when the window starting at index 0 becomes unfixable, every longer window starting at 0 is unfixable too — yet the brute force keeps extending anyway, and then starts over from scratch at index 1.

The key insight: cost of fixing = size minus the dominant character#

This is the Sliding Window + Frequency Count pattern. The reframe that powers it:

Pick any window. The cheapest way to make it uniform is to keep its most frequent character and flip everyone else. If maxFreq characters already match the dominant letter, exactly windowSize - maxFreq characters need to change. So a window is valid precisely when windowSize - maxFreq <= k.

That turns a fuzzy question ("can edits fix this?") into a numeric threshold — and numeric thresholds are exactly what sliding windows are built for. Grow the window while the count stays within budget; the moment it exceeds k, slide the left edge forward. Because each pointer only ever moves right, no window is ever examined twice.

The optimal solution#

This is the exact algorithm the interactive visualizer steps through. The frequency map is a 26-slot array (charCodeAt - 65 maps 'A'–'Z' to 0–25), and a helper computes validity fresh from the map:

Three structural details are worth internalizing:

• One decision per iteration. Most sliding-window code nests a shrink-while inside an expand-for. This version flattens it: each pass through the loop either records-and-expands (window valid) or shrinks by one (window invalid). Since every iteration advances exactly one pointer and neither pointer ever exceeds n, the loop runs at most 2n times.
• The map always mirrors [i..j] exactly. The first character is seeded before the loop (map[s.charCodeAt(0) - 65] = 1), and each expand increments the new s[j] only after checking j < s.length. totalCount inside the helper is therefore always the true window size — no separate size variable to drift out of sync.
• isWindowValid recomputes from scratch. It scans all 26 slots to get totalCount and maxCount each time. That's a fixed 26 units of work — a constant — which keeps the logic dead simple: no cached maximum to invalidate when the left edge moves.

Walkthrough: s = "ABAB", k = 1#

Return 3 — "ABA" (or "BAB") becomes "AAA" (or "BBB") with one flip.

Step 4 is the one to study. "ABAB" would need two replacements but the budget is one, so the window contracts by a single character rather than resetting. That single-step shrink is deliberate: a best-so-far of 3 is already banked in maxWindow, and the answer can only improve if some longer valid window exists later. Sliding — rather than restarting — preserves every chance of finding it.

Complexity#

The frequency map is 26 integers regardless of input size, so space is constant. The third row is a well-known micro-optimization (covered in the FAQ) — same asymptotic class, smaller constant, subtler correctness argument.

Common mistakes#

• Reading k as "at most k distinct characters." It's a count of edits, not of letter varieties. "ABCDE" with k = 4 is a perfectly valid window of length 5.
• Trying to simulate replacements. The moment you start mutating strings or branching on which letter to keep, you've left O(n) territory. The arithmetic windowSize - maxFreq already assumes the optimal choice — keep the dominant letter.
• Letting the map drift from the window. Every pointer move must be mirrored by exactly one increment or decrement. Note the if (j < s.length) guard before adding s[j] — without it, the final expansion reads past the end of the string.
• Resetting the window when it goes invalid. Shrinking by one and re-checking is enough. A full reset to i = j throws away a partially-valid prefix that might extend into the true answer.
• Off-by-one in the window size. The window [i..j] is inclusive on both ends, so its length is j - i + 1, not j - i.
• Hardcoding - 65 and then feeding lowercase input. 65 is the char code of 'A'. The LeetCode version guarantees uppercase; for lowercase use 97, and for mixed alphabets use a Map instead of a fixed array.

Where this pattern shows up next#

The budget-driven window — expand while a computed cost stays under a threshold, shrink when it doesn't — recurs across the two-pointer family:

• Two Sum — the entry point to the topic: one pass, with a hash structure standing in for the inner loop.
• Two Sum II - Input Array Is Sorted — two pointers converging under a numeric condition, the same "move exactly one pointer per step" discipline.
• Is Subsequence — the gentlest two-pointer walk over strings, good for cementing pointer-advance rules.
• Find the Index of the First Occurrence in a String — window-shaped string scanning where alignment, not a budget, decides validity.

Reading a trace table is one thing; watching the budget bar fill and the window snap back is another. Step through it interactively — the visualizer shows the frequency chart, the windowSize - maxFreq = replacements equation, and every expand/shrink decision live.

FAQ#

Why does windowSize minus maxFreq equal the replacements needed?#

Because the cheapest way to make a window uniform is to keep its most frequent character and change everything else. If the window has windowSize characters and maxFreq of them already match the dominant letter, the remaining windowSize - maxFreq characters each need exactly one flip. No strategy does better: keeping any less-frequent letter would force strictly more flips. So the window is fixable within budget exactly when windowSize - maxFreq <= k.

What is the time complexity of Longest Repeating Character Replacement?#

O(n) time and O(1) space. The loop runs at most 2n iterations because each iteration advances either the left or the right pointer, and each pointer can move at most n steps. The validity check scans a fixed 26-slot frequency array, which is a constant factor — O(26·n) collapses to O(n). Space is the 26-integer array plus a few scalars, independent of input length.

Do I ever need to know which characters get replaced?#

No. The problem asks only for the length of the best window, and the validity formula already encodes the optimal replacement strategy (keep the dominant character, flip the rest) without performing it. This is why the solution never builds a modified string — a common over-engineering trap that turns an O(n) counting problem into an exponential search.

What is the "stale maxFreq" optimization other solutions use?#

A popular variant caches the highest frequency ever seen and never decreases it when the window shrinks, avoiding the 26-slot rescan. It stays correct for a subtle reason: a stale (too-high) maxFreq can only make the window look more valid, which only matters when trying to beat the current best — and beating the best genuinely requires a higher real maxFreq, at which point the cache updates. Both versions are O(n); the recompute-fresh version taught here trades a constant factor for a validity check you can verify at a glance.

Why does the window shrink by only one character when it becomes invalid?#

Because the window was valid one step earlier — it just expanded past the budget by a single character, so removing a single character from the left is enough to get within one re-check of validity. More importantly, the best length seen so far is already recorded in maxWindow, so the window never needs to give back more ground than necessary. This is what makes the window effectively "slide": once it reaches the best size, it either grows or shifts right, never collapses.