The problem
Given a string s of uppercase letters and a number k, you may change any character to any other uppercase letter, at most k times in total.
Return the length of the longest stretch of one repeated letter you can make.
Examples
- Input
s = "ABAB", k = 2
- Output
4
- Input
s = "AABABBA", k = 1
- Output
4
Constraints
- 1 ≤ s.length ≤ 10⁵
shas only uppercase English letters.- 0 ≤ k ≤ s.length
The idea
For a window, the best plan is to keep its most common letter and change all the others. That takes window length − count of the most common letter changes. The window is usable if that is at most k.
Slide a window across, counting letters. When it needs more than k changes, move its left edge in by one. The window never has to shrink below its best size so far — only a window with a higher top count could be longer — so its size at the end is the answer.
- Time
- O(n)
- Space
- O(1) — 26 counters
Solution · every language run against every case
class Solution: def characterReplacement(self, s: str, k: int) -> int: count = [0] * 26 l = most = 0 # most: the highest count of one letter the window has reached for r, c in enumerate(s): count[ord(c) - 65] += 1 most = max(most, count[ord(c) - 65]) # Letters to replace = window length - most common letter. Too many? Slide. if (r - l + 1) - most > k: count[ord(s[l]) - 65] -= 1 l += 1 return len(s) - l # the window never shrinks, so its final size is the best