Medium Frequency Window Sliding Window
In plain English: You can change up to k letters in a string. Find the longest stretch you can make all the same character.
The window is valid when (window_size - max_freq_char) <= k. The key insight: we only need to track the global max frequency ever seen — if the window becomes invalid, we slide it (don't shrink), so max_freq never needs to decrease.
Prompt
Given a string s and an integer k, you can change at most k characters to any uppercase letter. Return the length of the longest substring containing the same letter after performing at most k replacements.
Try to write it from scratch before scrolling down.
Solution
def character_replacement(s, k):
count = {}
l = 0
max_freq = 0
result = 0
for r in range(len(s)):
count[s[r]] = count.get(s[r], 0) + 1
max_freq = max(max_freq, count[s[r]])
# window invalid: more than k chars need replacing
if (r - l + 1) - max_freq > k:
count[s[l]] -= 1
l += 1
result = max(result, r - l + 1)
return result
# Test: character_replacement("AABABBA", 1) == 4 ("AABA" or "ABBA")
# Test: character_replacement("ABAB", 2) == 4