682. Longest Run After k Replacements
You are given an uppercase string and a number k. You may replace at most k
characters with any letters you choose. Print the length of the longest run of
IDENTICAL characters you can produce.
Fix a window. To make it all one letter, keep whichever letter is already most common inside it and replace the rest, so the window is achievable when:
length - (count of the most common letter inside) <= k
That quantity never falls as the window widens, which is what makes a window work: once a window is too expensive, widening it further cannot help, so the left edge moves forward and never back.
The subtle part is that you never need to recompute the most common count when the window shrinks. The answer only ever grows, so a stale maximum can never produce a longer window than one that genuinely existed.
Constraints - `1 ≤ length of the string ≤ 100000` - `0 ≤ k ≤ length of the string` - The string contains only the characters `A` to `Z`.
Input
The first line contains the integer k.
The second line contains the string, made only of uppercase English letters.
Output
Print one integer: the length of the longest run of identical characters obtainable using at most k replacements.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.