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.

Details

Animated on: s="AABABBA", k=1 — longest substring where replacing at most k chars makes every char the same

Problem:Longest Repeating Character ReplacementMedium

Pattern:Sliding Window

Strings

step 1 / 7

[0]

[1]

[2]

[3]

[4]

[5]

[6]

s="AABABBA", k=1. left=0, maxFreq=0, best=0. Grow right through the string.

left=0· arr[0] = A

Pseudocode

1FUNCTION characterReplacement(s, k):
2  left = 0, maxFreq = 0, best = 0
3  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 right
8    best = the larger of best and the window length
9  END FOR
10  RETURN best
11END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 7 steps

s="AABABBA", k=1. left=0, maxFreq=0, best=0. Grow right through the string.
right=3: window [0,3]="AABA", counts A:3,B:1 → maxFreq=3. len4-3=1<=k, valid. best=4.
right=4: window [0,4]="AABAB", counts A:3,B:2. maxFreq stays 3 (B doesn't beat it). len5-3=2>k → invalid, must shrink.
Shrink: drop s[0]='A', left→1. Window [1,4]="ABAB" len4, 4-3=1<=k, valid again. best stays 4.
right=5: window [1,5]="ABABB", counts A:2,B:3. maxFreq stays 3 (tie). len5-3=2>k → shrink: drop s[1]='A', left→2. Window [2,5] len4, valid.
right=6: window [2,6]="BABBA", counts A:2,B:3. maxFreq stays 3. len5-3=2>k → shrink: drop s[2]='B', left→3. Window [3,6] len4, valid.
String exhausted. best stayed 4 — e.g. window [3,6]="ABBA": replace one char to make 4-in-a-row.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Repeating Character Replacement in the editor All Strings problems Back to roadmap