Longest Repeating Character Replacement

Problem

A text normalization pipeline needs to find the longest run of a single repeated character achievable with at most k in-place edits. Given a string of uppercase English letters and an integer k, return the length of the longest substring you can obtain where all characters are the same after performing at most k replacements.

Input: s = "ABAB",    k = 2  → 4   (replace both 'B's or both 'A's)
Input: s = "AABABBA", k = 1  → 4   ("AABA" with one replacement)
Input: s = "AAAA",    k = 0  → 4   (already uniform)

Solution

Approach: Variable-size window with the max-frequency validity trick.

A window can be turned into one repeated character by replacing every character that is not the most frequent one. The number of replacements needed is window_size - max_freq, where max_freq is the count of the dominant character. The window is valid when window_size - max_freq <= k. For each end, add s[end] to char_count, update max_freq = max(max_freq, char_count[s[end]]), and if (end - start + 1) - max_freq > k the window now needs too many replacements, so shrink: decrement char_count[s[start]] and advance start. Then record best = max(best, end - start + 1).

The subtle part is that max_freq is never lowered, even after shrinking removes copies of the dominant character. This is safe because we only care about windows larger than the current best. A stale (too-high) max_freq can only make the validity test pass for windows up to the size where it was genuinely true, and any window it wrongly admits is no larger than one already counted - so best is never inflated. Keeping max_freq lazy avoids an O(26) recomputation each step.

Trace "AABABBA" with k=1: the window expands to "AABA" (max_freq for 'A' is 3, size 4, replacements 1 <= 1), giving best 4 - the answer.

Edge cases: k >= len(s) makes the whole string valid (best = len(s)). A single character returns 1. All-distinct input with small k caps the window at k + 1.

Complexity: O(n) time, O(1) space - each pointer advances at most n times; the frequency dict holds at most 26 uppercase-letter entries.