Write character_replacement(s: str, k: int) -> int.
s contains only uppercase letters A-Z. You may change at most k characters of s into any other uppercase letter. Return the length of the longest contiguous block of identical letters you can end up with.
Example: s = "BAAB", k = 1 gives 3 (change one B to get "AAAB" or "BAAA"). s = "ABCDE", k = 0 gives 1. s = "AABABBA", k = 1 gives 4.
Constraints: 1 <= len(s) <= 2 * 10^5, 0 <= k <= len(s).
⭐ Bonus: trying every substring still passes; a speed test earns a star in O(n) (O(26·n) is fine).
Show hint
a block can be made uniform when its length minus the count of its most common letter is at most k. Look at contiguous blocks that grow on the right and shrink on the left only when they stop qualifying.