347. Longest Repeating Character Replacement
You are given a string s made of uppercase English letters and an integer k.
You want to find a substring of s and turn it into a block of one single repeated letter. You are allowed to overwrite at most k characters of that substring (each overwrite changes one position to any letter you like).
Return the length of the longest substring that can be made uniform this way.
Put differently: a window of s is fixable when the count of everything except its most common letter is at most k. Find the widest fixable window.
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Overwrite the two 'A's (or the two 'B's) and the whole string becomes uniform — length 4.
Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: The window "AABA" has three 'A's and one 'B'; one overwrite makes it "AAAA". No window of length 5 can be fixed with a single change.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of uppercase English letters only
- 0 ≤ k ≤ s.length
Hints:
For any window, the cheapest way to make it uniform is to keep its most frequent letter and overwrite the rest. So a window of length L with max letter-count m needs L - m changes, and it is fixable exactly when L - m <= k.
The condition L - m <= k is (nearly) monotone: growing a window can only make it harder to fix, shrinking it easier. That shape is the signature of a sliding window with two pointers and a 26-slot count array.
Classic subtlety: when the window slides, you don't have to decrease your recorded max count. A stale (too large) max can only keep the window size the same, never wrongly grow it — and the true best window is still found when its letter's count peaks.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "ABAB", k = 2
Expected output: 4