Longest Repeating Character Replacement Visualizer & Step-by-Step Algorithm Solution

Find the length of the longest substring containing the same letter you can get after performing at most k character replacements using a dynamic sliding window.

Category: sliding-window | Difficulty: Medium

Tags: Sliding Window, Two Pointers, Frequency Map

Longest Repeating Character Replacement

String Characters (s)
L, R
A
0
B
1
A
2
B
3
Window Frequencies
(Empty Map)
100%
state
k2
left0
right0
windowLen1
maxFreq0
replacementsNeeded1
longest0
Initialization
1/18
Explanation

Initialize count map, maxFreq = 0, longest = 0, left = 0, k = 2.

Source Code
1function characterReplacement(s, k) {
2 const count = new Map();
3 let maxFreq = 0;
4 let longest = 0;
5 let left = 0;
6 for (let right = 0; right < s.length; right++) {
7 const char = s[right];
8 count.set(char, (count.get(char) || 0) + 1);
9 maxFreq = Math.max(maxFreq, count.get(char));
10 while ((right - left + 1) - maxFreq > k) {
11 count.set(s[left], count.get(s[left]) - 1);
12 left++;
13 }
14 longest = Math.max(longest, right - left + 1);
15 }
16 return longest;
17}