Find the longest substring with at most k character replacements.
This problem follows the Variable Window + Count pattern, commonly found in the Sliding Window category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Window size - max frequency char count <= k means window is valid.
You don't need to decrease maxFreq when shrinking — if it's wrong, the window just won't grow, but it can never give a wrong answer.
count = {}
left = 0
maxFreq = 0
result = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
maxFreq = max(maxFreq, count[s[right]])
if (right - left + 1) - maxFreq > k:
count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return resultPractice Longest Repeating Character Replacement and similar Sliding Window problems with flashcards. Build pattern recognition through active recall.
Practice this problem