Description
In an uppercase English string, replace at most k letters to obtain the longest contiguous block of one repeated letter.
Solution
from collections import Counter
def character_replacement(s, k):
counts = Counter()
left = most = best = 0
for right, char in enumerate(s):
counts[char] += 1
most = max(most, counts[char])
while right-left+1-most > k:
counts[s[left]] -= 1
left += 1
best = max(best, right-left+1)
return bestExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
["ABAB",1]- Output
3
One change makes ABA or BAB uniform.
Example 2
- Input
["AAAA",0]- Output
4
No replacements are needed.
Example 3
- Input
["ABCD",2]- Output
3
Two replacements make any length-three window uniform.
Approach
Maintain a window and its highest historical letter frequency. Shrink when length minus that frequency exceeds k.
Time & space
O(n) time; O(1) space for 26 letters.