0
L
Given a string and an allowance of k character replacements, find the longest substring you can make entirely of one repeated character — a classic variable-size sliding window where the window stays valid while windowLength − maxFreq ≤ k.
You have a string of uppercase letters and can change at most k characters. Return the length of the longest substring that consists of a single repeated letter after those replacements.
Example: s="AABABBA", k=1. If you replace the B at index 5 with A, you get AAAA spanning indices 0–3 (length 4). Answer: 4.
windowLength − maxFreq, where maxFreq is the count of the most frequent character. The window is valid as long as this value is ≤ k. You never need to know which character wins — only how many others need changing.maxFreq as L advances. This is both unnecessary and costly. Because you only care about beating the current best length, the window only needs to grow— if it can't grow, it slides as a unit (L and R both advance by 1). A stale maxFreq is fine: it only allows the window to move forward, never backward.L = 0, maxFreq = 0, best = 0, counts map empty.s[R] to counts. Update maxFreqif this char's new count exceeds it.(R - L + 1) - maxFreq > k, the window needs too many replacements. Evict s[L] from counts and advance L. Do not update maxFreq.best = Math.max(best, R - L + 1). Because the window can only grow or slide (never shrink), the window size only increases when we find a strictly better answer.best.The "never shrink maxFreq" trick keeps the inner loop from ever running more than once per iteration — L advances at most once per R step, so total work is O(2n) = O(n). Space is O(26) = O(1) for an uppercase-only alphabet.
maxFreq (highest count in window). Window is valid while windowLen − maxFreq ≤ k.function characterReplacement(s: string, k: number): number {
const counts: Record<string, number> = {};
let maxFreq = 0;
let best = 0;
let L = 0;
for (let R = 0; R < s.length; R++) {
const ch = s[R];
counts[ch] = (counts[ch] ?? 0) + 1;
if (counts[ch] > maxFreq) maxFreq = counts[ch];
// windowLen - maxFreq = number of replacements needed
if (R - L + 1 - maxFreq > k) {
// slide the window: remove leftmost char, keep maxFreq unchanged
counts[s[L]]--;
L++;
}
best = Math.max(best, R - L + 1);
}
return best;
}counts tracks character frequencies inside the current window. maxFreq is the highest any single character appears in the window (it only ever grows). Lis the window's left edge.maxFreq. This is the only place maxFreq increases.(R - L + 1) - maxFreq is the minimum replacements needed. If that exceeds k, evict s[L] and advance L by one. Crucially, we do not recompute maxFreq here — a potentially stale value is safe because it only allows the window to advance, never retrograde.R - L + 1. Because the window never shrinks, best only updates when the window actually grew past the previous best — so you could write this as an if instead of Math.max and it would still be correct.L advances at most once per iteration of the outer loop, so total pointer moves ≤ 2n. O(26) = O(1) space for the counts map over uppercase letters; O(n) in the worst case for arbitrary characters.Map<string, number> instead of a fixed array; time stays O(n), space becomes O(k) distinct chars.bestL whenever best updates and return s.slice(bestL, bestL + best).best. A window the same size as before with a stale maxFreq will always fail the validity check and slide — it will never be accepted as a new best.windowLen − maxFreq ≤ k is character-set agnostic. Just swap in a suitable count structure.| "replace at most k characters" in a string | sliding window, validity = windowLen − maxFreq ≤ k |
| "flip at most k zeros / bits" | same window formula: windowLen − count(dominant) ≤ k |
| window slides but never shrinks | stale maxFreq trick — only care about growing best |
| "longest substring / subarray with at most k changes" | variable-size sliding window, evict one left element when invalid |
const counts: Record<string, number> = {};
let maxFreq = 0, best = 0, L = 0;
for (let R = 0; R < s.length; R++) {
counts[s[R]] = (counts[s[R]] ?? 0) + 1;
maxFreq = Math.max(maxFreq, counts[s[R]]);
if (R - L + 1 - maxFreq > k) {
counts[s[L]]--;
L++;
}
best = Math.max(best, R - L + 1);
}
return best;windowLength − maxFreq ≤ k. The left side counts characters that must be replaced.windowLen − maxFreq represent?s="AABABBA", k=1, what length does the algorithm return?k = 0?maxFreqmight be "stale" — larger than any real frequency in the final window. Is the returned best still correct?