Longest Repeating Character Replacement

Problem

You are given a string s of uppercase English letters and an integer k. You may overwrite up to k positions with any uppercase letter you like. Return the length of the longest contiguous block consisting of a single repeated letter that can be produced this way.

• s has between 1 and 100,000 characters, all uppercase A-Z.
• k is a non-negative integer no larger than the length of s.

Examples

• s = "QQZQZZQ", k = 1 → 4. Overwrite the Z in QQZQ (or the Q in ZQZZ) to get a uniform block of four; no block of five can be fixed with one edit.
• s = "XYXY", k = 2 → 4. Two edits are enough to turn the whole string into XXXX or YYYY.
• s = "PQRST", k = 0 → 1. Nothing can be changed and no two neighbours already match.

Hints

1. For a fixed window, which letter should you keep and which ones should you overwrite? How many overwrites does that take?
2. A window is fixable when window length - count of its most common letter <= k. Does this property stay true when you shrink the window?
3. Sliding window with a 26-entry count table; expand hi, and when the window needs more than k edits, move lo one step. The window never needs to shrink below the best length already found.