Pattern visualizer
Longest Repeating Character Replacement
Sliding window tracking the count of the window's most frequent character. A window of length L is valid once you can replace at most k characters — i.e. L - maxFreq <= k. Grow the window; shrink from the left only when it stops being valid. Reach for it on 'longest substring under a replacement budget' problems. Animated on: s="AABABBA", k=1 — longest substring where replacing at most k chars makes every char the same.
Strings
step 1 / 7
A
[0]A
[1]B
[2]A
[3]B
[4]B
[5]A
[6]line 2
s="AABABBA", k=1. left=0, maxFreq=0, best=0. Grow right through the string.
Pseudocode
1FUNCTION characterReplacement(s, k):2 left = 0, maxFreq = 0, best = 03 make an empty count table (character -> how many in the window)4 FOR right from 0 to the length of s:5 add one to the count of s[right]6 maxFreq = the larger of maxFreq and the count of s[right]7 WHILE (window length) - maxFreq > k: subtract one from the count of s[left] and move left one step right8 best = the larger of best and the window length9 END FOR10 RETURN best11END FUNCTION
← / → step · space play · Home restart