Given a string s of uppercase English letters and an integer k, you may change at most k characters to any letter you like. Return the length of the longest substring you can make consist of a single repeated letter.
Examples
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: change both A's (or both B's) and the whole string matches.
Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: "ABBA" with the lone A flipped gives "BBBB".
Example 3:
Input: s = "AAAA", k = 2
Output: 4
Example 4:
Input: s = "ABCDE", k = 1
Output: 2
Constraints
1 <= s.length <= 10^5
s consists of uppercase English letters.
0 <= k <= s.length
Prerequisites
Sliding windows — a left and right edge moving forward only, and the invariant that decides when the left edge advances. Hash maps or fixed-size counts for what the window currently holds.
How to think about it
1. Window Minus Its Most Common Letter Optimal
Intuition
A window can be made uniform when the letters that are not its most common one number at most k — that is, width minus the highest count is within budget. Grow the right edge, and when the budget is blown, slide the left edge. The subtle part: the highest count is never lowered when the window shrinks, and it does not need to be, because a stale value can only make the window look too expensive, never too cheap — so the answer is never over-reported.
Algorithm
1. Count letters inside the window; track the highest count seen. 2. Extend the right edge, updating that count. 3. While width minus the highest count exceeds k, slide the left edge up one. 4. The widest window that was ever valid is the answer.