Longest Repeating Character Replacement
MediumSliding window
You are given a string s of uppercase letters and an integer k. You may change at most k characters of s, each to any uppercase letter.
Return the length of the longest substring, a run of consecutive characters, that can be made of one repeated letter after your changes.
Examples
Input: s = "BAAAB", k = 1 Output: 4
Change the first B to A, and AAAA is four long.
Input: s = "XYZ", k = 0 Output: 1
With no changes allowed, the longest run of one letter is one letter.
Constraints
1 ≤ s.length ≤ 10⁵0 ≤ k ≤ s.lengthsuses uppercase English letters only.
Stuck?
Hint 1
A window can become one letter when its length minus the count of its most common letter is at most k.
Hint 2
Slide a window with letter counts. Grow it on the right, and when it needs more than k changes, move the left edge in by one.
The idea
A window can become one repeated letter when the letters that are not its most common letter number at most k, because those are the ones to change. Slide a window along s, growing it on the right, and move its left edge in whenever it would need more than k changes.
Time O(n)Extra space O(1): 26 counts
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
count holds how many times each letter appears in the window, from start to i. most is the highest count any letter has reached in it.
function characterReplacement(s, k) { const count = {}; let start = 0; let most = 0; let best = 0; for (let i = 0; i < s.length; i++) { count[s[i]] = (count[s[i]] || 0) + 1; most = Math.max(most, count[s[i]]); if (i - start + 1 - most > k) { count[s[start]]--; start++; } best = Math.max(best, i - start + 1); } return best;}The trap
Taking the most common letter in the whole string and adding k treats the letters as if they could be moved next to each other. That works when the copies of that letter already sit together. When they are spread out, the letters between them also need changing, and the answer comes out too big.
function characterReplacement(s, k) { const count = {}; for (const c of s) count[c] = (count[c] || 0) + 1; // the most common letter anywhere, as if the letters could be moved together return Math.min(s.length, Math.max(...Object.values(count)) + k);}