Longest Repeating Character Replacement
Part of Practice: Longest Valid Windows
You get a string s of uppercase English letters and a number k. You may change at most k characters of the string to any other letter. Return the length of the longest substring you can produce that consists of a single repeated letter.
Put differently: find the longest window of s in which all characters can be made identical using at most k edits. The string can be up to 10^5 characters, so trying every window is too slow.
Examples
- Input:
- s = "ABAB", k = 2
- Output:
- 4
Change both A's to B (or both B's to A) to get "BBBB" — the whole string, length 4.
- Input:
- s = "AABABBA", k = 1
- Output:
- 4
Take the window "AABA" (positions 0-3): one edit turns the B into A, giving "AAAA", length 4. The window "BABB" (positions 2-5) also works: one edit gives "BBBB". No 5-wide window is fixable with a single edit.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.