Longest Repeating Character Replacement

The input is an uppercase string s and a budget k. One operation overwrites a single character with any other uppercase letter, and you may spend up to k operations.

Goal: return the length of the longest substring that can be made entirely of one repeated letter within that budget.

We use a Sliding Window to check if a valid window exists. A window (substring) is valid if we can turn it into all same characters using at most k replacements.

Logic:

1. Validity Check: Replacements Needed = Window Length - Count of Most Frequent Char.
   • If Replacements Needed <= k, the window is valid. We try to expand it (increment right).
   • If Replacements Needed > k, the window involves too many changes. We perform one shrink step (increment left) to try and make it valid again.
2. We maintain a frequency map (or array of size 26) to track counts of characters in the current window.
3. We keep track of max_count, the highest count any character has reached in a window so far. It is never decreased, which is why the map is never re-scanned; the section below explains why a stale value still gives the right answer.

Watch how the window expands and only shrinks when the number of replacements needed exceeds k.