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).

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: replace one 'B' to make "AABA".

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 maximum frequency of any single character in the window.

The number of replacements needed is windowSize - maxFreq. If that exceeds k, shrink from the left.

Invariant: windowSize - maxFreq <= k for the current window.

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

• Invariant: windowSize - maxFreq <= k for the current window.
• The window state exactly matches the elements in s[l..r].
• Shrinking/expanding preserves validity, so any recorded window is correct.
• The best recorded window is optimal because all candidate windows are considered.

Trace (hand walkthrough)

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

One answer: replace one 'B' to make "AABA".

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

• Recomputing maxFreq on every shrink (not needed; it can be stale and still correct).
• Using this approach for non-fixed alphabets without adapting the count structure.

Complexity

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

Implementation notes (Go)

• Track maxFreq of any char in the window.
• Window is valid while len - maxFreq <= k; do not recompute max on shrink.