Longest Repeating Character Replacement
Problem
The string contains uppercase letters. You may replace at most k characters with any letter. Return the length of the longest substring you can make that consists of a single repeated letter.
Example 1
Input: s = "ABAB", k = 2 Output: 4
Example 2
Input: s = "AABABBA", k = 1 Output: 4
Replace the A at index 3: "AABBBBA" contains "BBBB".
Test cases
Case 1
Input: "ABAB", 2 Expected: 4
Case 2
Input: "AABABBA", 1 Expected: 4
Case 3
Input: "A", 0 Expected: 1
View solutionHide solution1 approach
1. Window with max frequency
Time O(n)Space O(26)
A window is valid when length − (count of its most common char) ≤ k. maxFreq never needs to decrease: a smaller one cannot produce a longer answer.
function characterReplacement(s, k) { const cnt = new Array(26).fill(0); let l = 0, maxFreq = 0, best = 0; for (let r = 0; r < s.length; r++) { maxFreq = Math.max(maxFreq, ++cnt[s.charCodeAt(r) - 65]); while (r - l + 1 - maxFreq > k) cnt[s.charCodeAt(l++) - 65]--; best = Math.max(best, r - l + 1); } return best;}