Problem. You may replace at most k characters in a string. Return the length of the longest substring that can be made entirely of one repeated character.
This is the classic window validity by mismatch count pattern.
Examples:
s = "ABAB",k = 2→4s = "AABABBA",k = 1→4s = "AAAA",k = 0→4
Solution. Inside any window, the minimum number of replacements needed is window_size - max_frequency_of_any_character. Keep the window as large as possible while that value stays at most k.
from collections import defaultdict
def character_replacement(s, k):
counts = defaultdict(int)
left = 0
max_freq = 0
best = 0
for right, char in enumerate(s):
counts[char] += 1
max_freq = max(max_freq, counts[char])
while (right - left + 1) - max_freq > k:
counts[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
O(n) time, O(alphabet) space.
Gotchas.
max_freqis allowed to be stale when the left edge moves; the window logic still stays correct and O(n).- This is length-only, so you do not need to reconstruct the final substring.
- Do not count the number of distinct characters; only the most frequent one matters.