MediumLongest run you can make uniform with at most k replacements — sliding window.
You are given a string s and an integer k. You may replace at most k characters with any uppercase letter. Return the length of the longest substring that can be made up of a single repeated character after those replacements.
Walkthrough
try:
Longest window you can make all-one-letter by replacing at most k characters. Valid when (window length − most common) ≤ k.
0
1
2
3
4
5
6
A
A
B
A
B
B
A
·
·
·
·
·
·
·
counts—
window0replace0best0
windowrightmost common
1
function characterReplacement(s, k) {
2
const count = {};
◄
3
let left = 0, maxFreq = 0, best = 0;
4
for (let right = 0; right < s.length; right++) {
5
const c = s[right];
6
count[c] = (count[c] || 0) + 1;
7
maxFreq = Math.max(maxFreq, count[c]);
8
while ((right - left + 1) - maxFreq > k) {
9
count[s[left]]--;
10
left++;
11
}
12
best = Math.max(best, right - left + 1);
13
}
14
return best;
15
}
count = {}
step 0 / 39
line 2
count = {}
Track how many of each letter are inside the current window.
Intuition
A window can be made uniform if the number of characters to replace — its length minus the count of its most frequent letter — is at most k.
Grow a window to the right, keeping a tally of letter counts and the highest count seen (maxFreq).
Whenever (window length − maxFreq) exceeds k, the window needs too many replacements: shrink it from the left until it is valid again.
Track the largest valid window length. (maxFreq is never decreased on shrink; that is fine because the answer only ever grows.)
The algorithm
01Keep a count map, a left pointer, maxFreq, and best.
02For each right, add s[right] to the counts and update maxFreq.
03While (right − left + 1) − maxFreq > k, remove s[left] and advance left.
04Update best with the current window length; return best.