Longest Repeating Character Replacement

Given a string s of uppercase English letters and an integer k, you can replace at most k characters. Return the length of the longest substring that can be turned into all the same character using at most k replacements.

A sliding window with a running max frequency solves this in O(n).

Why this is worth learning

The nondecreasing max-frequency optimization does not claim the current window is always truly feasible. It preserves the best attainable length, using a historical frequency as a certificate for when the best can grow.

Before coding: one-minute experiment

For "AABABBA" with k=1, is every maintained window necessarily valid when maxFreq is not reduced?

Function signature

func CharacterReplacement(s string, k int) int

Inputs / outputs

• s: uppercase English letters.
• k: maximum number of replacements.
• Return: length of the longest valid substring.

Example

s = "AABABBA", k = 1
Output: 4

One answer: take window "AABA" and replace its B with A to make "AAAA".

Constraints

• 0 <= len(s) <= 100_000
• 0 <= k <= len(s)

Core idea (near-solution)

Maintain a window [l, r] and the count of each letter inside it. Let maxFreq be the historical maximum frequency observed during expansions; it is deliberately not reduced while the left edge moves.

Using the true current maximum would give the exact replacement cost. With the retained historical maximum, windowSize - maxFreq is instead a lower bound used to control candidate length. If that exceeds k, shrink from the left. A retained current window need not itself be feasible; the correctness proof below explains why the best reported length remains attainable.

Invariant after shrinking: windowSize - historicalMaxFreq <= k. Counts still describe the current window, but historicalMaxFreq may exceed its true maximum. Do not infer that every retained window is feasible.

Algorithm (step-by-step)

1. Initialize l = 0, best = 0, maxFreq = 0, and a 26-count array.
2. For each r from 0 to len(s)-1:
   • Increment the count for s[r] and update maxFreq.
   • While (r-l+1) - maxFreq > k:
     • Decrement the count for s[l] and increment l.
   • Update best = max(best, r-l+1).
3. Return best.

Correctness sketch

Let M be the nondecreasing historical maximum frequency. At each expansion, length grows by one and M grows by zero or one. Because the previous length was at most M+k, at most one removal restores that inequality; maintained length never decreases. Before the first removal, M is exact and every retained length has a feasible witness. After the first removal, length equals M+k. While M is unchanged, each expansion then forces one removal, so a stale M cannot grow the reported best. A later increase in retained length requires M to increase: the newly added character actually has that new count, and the expanded length is at most newM+k, so this growth has a genuinely feasible witness. Finally, whenever removal occurs, length-M>k. Since M is at least the current true maximum, that start is genuinely infeasible; extending a fixed-start window cannot decrease length minus its true maximum frequency, so it cannot become feasible later. Thus no optimal future start is discarded, and every new best length has a feasible witness. The current window itself need not always be feasible. Recomputing the exact maximum over 26 counts is another valid linear-time approach for this fixed alphabet, with a simpler current-feasibility invariant.

Trace (hand walkthrough)

Example input:
s = "AABABBA", k = 1
Output: 4

One answer: take window "AABA" and replace its B with A to make "AAAA".

Walk:
- window "AABA" (r=0..3): maxFreq=3, size-maxFreq=1 <= k, best=4
- add B -> "AABAB" size=5, maxFreq=3, 5-3=2>k -> move l to 1 ("ABAB")
- add B -> window "ABABB" size=5, maxFreq=3, 5-3=2>k -> move l to 2 ("BABB")
- best remains 4

Pitfalls to avoid

• Calling the historical maximum the current maximum. Recomputing over all 26 active counts is a valid alternative, but it uses a different invariant.
• Using this approach for non-fixed alphabets without adapting the count structure.

Debugging lens

Cross-check every substring on short uppercase strings. Do not explain stale maxFreq as the current exact maximum. With k=0 the result must equal the longest run.

Complexity

• Time: O(n)
• Extra space: O(1) (26 counts).

Implementation notes (Go)

• Track the historical maxFreq observed during expansions, not necessarily the true current maximum.
• The scan keeps len - maxFreq <= k using a historical, nondecreasing maximum. It caps candidate length; the historical deficit is a lower bound on actual replacements, not proof that every current window is valid. Do not recompute max on shrink in this optimized variant.

Reconstruction checkpoint

For "AABABBA" with k=1, is every maintained window necessarily valid when maxFreq is not reduced?

Return to Sliding Window · Module quiz