The problem. Given a string s of uppercase letters and an integer k, you may change at most k characters to any other uppercase letter. Return the length of the longest substring that can then consist of one repeated letter.
s = "ABAB", k = 2 -> 4 (replace both A's, or both B's)
s = "AABABBA", k = 1 -> 4 ("AABA" -> "AAAA")
s = "AABBBCC", k = 0 -> 3 ("BBB", no changes allowed)Look at any window. The cheapest way to make it all one letter is to keep its most common letter and replace the rest. So a window works exactly when length - (count of its most common letter) <= k.
That condition behaves well as the window moves: growing the window can only make it harder to satisfy, and shrinking it from the left makes it easier. That's the shape a variable-size sliding window needs. Grow the right edge one letter at a time; whenever the window needs more than k replacements, shrink the left edge until it doesn't; and remember the longest window seen.
function characterReplacement(s, k) { let best = 0; for (let i = 0; i < s.length; i++) { const count = new Array(26).fill(0); let maxFreq = 0; for (let j = i; j < s.length; j++) { const c = s.charCodeAt(j) - 65; maxFreq = Math.max(maxFreq, ++count[c]); if (j - i + 1 - maxFreq <= k) best = Math.max(best, j - i + 1); // s[i..j] works } } return best;}Time O(n²), space O(1). Every pair (start, end) is looked at once.
The window grows right; when it needs more than k replacements, it shrinks from the left. Try k = 0.
function characterReplacement(s, k) { const count = new Array(26).fill(0); let left = 0, best = 0; for (let right = 0; right < s.length; right++) { count[s.charCodeAt(right) - 65]++; // 'A' is 65 // To make the window one letter, replace everything except its most common letter. while (right - left + 1 - Math.max(...count) > k) { count[s.charCodeAt(left) - 65]--; // too many to replace: shrink from the left left++; } best = Math.max(best, right - left + 1); } return best;}Time O(n), space O(1). left and right each move at most n times; finding the largest of 26 counts is a constant amount of work per step.
A famous refinement keeps maxFreq as a running maximum that never goes down, and shrinks with if instead of while. It looks wrong — the window's real maximum can drop — but the answer only improves when a window beats the best so far, and that needs a genuinely higher maxFreq. It saves the 26-count scan; mention it if asked.
