You're given a string s and a budget k. You may replace at most k characters in s with any other letters. After those replacements, what is the length of the longest run of a single repeated character you can produce? You don't have to return the substring itself — just its length. Think of it as a contiguous stretch of the string where, by spending up to k swaps, every character becomes the same letter.
// s: string — the input (assume uppercase A–Z letters)
// k: number — the maximum number of characters you may replace (k >= 0)
// returns: number — the length of the longest substring that becomes
// a single repeated character after at most k replacements
function longestRepeatingSubstringAfterReplacements(s, k): number;The substring must be contiguous — you pick a start and end index, and within that window you replace up to k characters so the whole window is one letter.
// Replace both 'B's with 'A' (or both 'A's with 'B') → "AAAA" or "BBBB", length 4.
longestRepeatingSubstringAfterReplacements('ABAB', 2); // → 4// Window "BABB" (indices 2–5): replace the one 'A' at index 3 with 'B' to get
// "BBBB" using one swap. Length 4. No valid window of length 5 exists for k=1.
longestRepeatingSubstringAfterReplacements('AABABBA', 1); // → 4// With no replacements allowed, you can only use a run that already exists.
// The longest existing run of one character is "BBB", length 3.
longestRepeatingSubstringAfterReplacements('AABBBCC', 0); // → 3// Every character is already the same — no swaps needed, the whole string counts.
longestRepeatingSubstringAfterReplacements('BBBBBB', 2); // → 6A–Z. You don't need to handle lowercase, digits, or other characters — though the sliding-window approach generalizes to any alphabet (see the solution's Going further).k replacements, not exactly k. If a window is already uniform you spend zero swaps; you never have to use the full budget.k can be 0. With no swaps allowed, the answer is the longest run of a single repeated character that already exists in s.0. No window, no length.k may exceed the string length. If your budget is at least the length of s, you can turn the entire string into one letter — the answer is s.length.You'll find the length of the longest contiguous stretch of s that can become a single repeated letter after replacing at most k characters — using a window that slides across the string exactly once.
You have a string and a budget of k swaps. Within some contiguous window, you want every character to end up the same letter. The cheapest way to make a window uniform is to keep whichever letter already appears most often inside it and replace all the others. So the number of swaps a window costs is its length minus the count of its most-common letter. If that cost fits in your budget k, the window is achievable. Your job is to find the longest such window.
Concretely: in the window "BABB", B appears 3 times and A once. To make it all B, you replace the single A — one swap. With k = 1, that window is achievable, so it contributes a length of 4 to your answer.
Track a window with two pointers, left and right. Inside it, keep a count of each character and the largest of those counts — call it maxFreq. The characters you'd have to replace to make the window uniform is windowLength - maxFreq. A window is valid when that number is at most k.
The whole algorithm is: push right forward one character at a time, growing the window; whenever the window becomes invalid, pull left forward to shrink it back; the answer is the largest valid window length you ever see.
The obvious move is to check every possible substring. For each start index i and each end index j, count the characters in s[i..j], find the most common one, and see whether the rest fit in k.
function brute(s, k) {
let best = 0;
for (let i = 0; i < s.length; i++) {
const count = {};
let maxFreq = 0;
for (let j = i; j < s.length; j++) {
count[s[j]] = (count[s[j]] || 0) + 1;
maxFreq = Math.max(maxFreq, count[s[j]]);
const len = j - i + 1;
if (len - maxFreq <= k) best = Math.max(best, len); // window achievable?
}
}
return best;
}This is correct — it literally considers every window. But it's O(n²): there are about n²/2 substrings, and even though we reuse the count map as j grows (so we don't recount from scratch within one i), the outer loop restarts that map for every new i. On a 10,000-character string that's ~50 million iterations. The waste is that each new starting index throws away everything we learned about overlapping windows and recounts the same characters again.
Instead of restarting for every start index, keep one window and move both edges forward only. Each character enters the window once (when right passes it) and leaves at most once (when left passes it), so the whole scan is O(n).
function longestRepeatingSubstringAfterReplacements(s, k) {
const count = {}; // count[c] = occurrences of c in the current window
let left = 0; // left edge of the window
let maxFreq = 0; // largest single-character count seen in any window so far
let best = 0; // longest valid window length found
for (let right = 0; right < s.length; right++) {
const c = s[right];
count[c] = (count[c] || 0) + 1; // the new char enters the window
maxFreq = Math.max(maxFreq, count[c]); // it may be the new most-common char
// windowLength - maxFreq is the number of chars we'd replace.
// If that exceeds k, the window is invalid: drop the leftmost char.
if ((right - left + 1) - maxFreq > k) {
count[s[left]]--;
left++;
}
// After the (at most one) shrink, the window [left..right] is valid.
best = Math.max(best, right - left + 1);
}
return best;
}
module.exports = { longestRepeatingSubstringAfterReplacements };A few choices here are worth pausing on.
Why if and not while for the shrink. The window grows by exactly one character per iteration, so it can become invalid by at most one over-budget character at a time. A single left++ per step is enough to keep pace — we never need to shrink twice in one iteration. This also means left advances at most n times total across the whole run, which is what keeps the algorithm linear. A while loop here would also be correct, but the if makes the "window never shrinks below the best" behaviour explicit (more on that in the gotchas).
Why maxFreq is never decreased, even when left moves past the most-common character. This is the subtle part. When we shrink, we decrement count[s[left]], but we do not recompute maxFreq. It can therefore be momentarily larger than the true maximum count in the current window. That looks like a bug, but it's deliberate and safe — explained in full in the walkthrough and gotchas below. The short version: a stale-high maxFreq only ever lets the window keep its current width; it can never produce a window wider than one that was genuinely valid earlier, so best is never inflated.
Why best = Math.max(best, ...) every iteration. Writing best = right - left + 1 directly would be wrong on the rare step where the window held flat — taking the max is the safe, clear way to record the widest window seen, and on a growing step it captures the new width immediately.
Let's trace s = "AABABBA", k = 1. Notation: the window is [left..right] inclusive.
right=0 c='A' count={A:1} maxFreq=1
len 1 - 1 = 0 <= 1 valid window "A" best=1
right=1 c='A' count={A:2} maxFreq=2
len 2 - 2 = 0 <= 1 valid window "AA" best=2
right=2 c='B' count={A:2,B:1} maxFreq=2
len 3 - 2 = 1 <= 1 valid window "AAB" best=3
right=3 c='A' count={A:3,B:1} maxFreq=3
len 4 - 3 = 1 <= 1 valid window "AABA" best=4
right=4 c='B' count={A:3,B:2} maxFreq=3
len 5 - 3 = 2 > 1 INVALID
drop s[left]=s[0]='A': count={A:2,B:2}, left=1
window "ABAB" (len 4) best=4
right=5 c='B' count={A:2,B:3} maxFreq=3
len 5 - 3 = 2 > 1 INVALID
drop s[left]=s[1]='A': count={A:1,B:3}, left=2
window "BABB" (len 4) best=4
right=6 c='A' count={A:2,B:3} maxFreq=3
len 5 - 3 = 2 > 1 INVALID
drop s[left]=s[2]='B': count={A:2,B:2}, left=3
window "ABBA" (len 4) best=4
return 4
Now look at the steps after right=3. Once maxFreq reached 3 (at right=3, the three As in "AABA"), it never goes back down — even at right=6 where the window "ABBA" has a true max count of only 2. At right=6, maxFreq is stale: it's still 3 from a window that no longer exists.
Why doesn't that break anything? Once the window reached width 5 and was invalid (at right=4), we shrink by one and the window stays width 4 from then on. A stale-high maxFreq makes the validity check easier to pass, so the window holds its width but never grows wider than it was. And the only width that matters for the answer is the widest valid window we ever found — recorded back at right=3 when maxFreq was honestly 3. The stale value can't manufacture a window wider than a genuinely valid one: best only increases when right - left + 1 exceeds the previous best, which requires the window to actually grow past its old width. The first time any width L was reached, maxFreq was a real count; and maxFreq can only rise from there, so a stale value never unlocks a new, larger width that wasn't already legitimately reachable.
windowLength - maxFreq <= k, not anything involving the second-most-common count. The chars you replace are everything that isn't the most-common letter: windowLength - maxFreq. If that's within budget k, you can make the window uniform. Get this expression wrong and every answer is off.maxFreq does not need to be perfectly accurate after a shrink — and recomputing it would cost performance for zero correctness gain. You might be tempted to scan all counts to refresh maxFreq whenever left moves. It's unnecessary: a stale-high maxFreq only lets the window keep its width, never exceed the best already recorded. Recomputing it on every shrink would add an O(alphabet) factor for no benefit. Leave it alone.k = 0 is the "longest existing run" problem. With no swaps, windowLength - maxFreq <= 0 forces windowLength === maxFreq, i.e. every character in the window is the same. The algorithm degrades gracefully into "find the longest run of one repeated character" — no special-casing needed.count[s[right]] when a character enters and decrement count[s[left]] when one leaves. Forget the decrement and the counts drift upward, maxFreq inflates without bound, the window never effectively shrinks, and you'll return numbers larger than the string.if removes at most one, the window's width is monotonically non-decreasing: it stays flat on an invalid step or grows on a valid one, but it never gets smaller. That's why a single if suffices and why left advances at most n times total.s never enters the loop, so best stays 0 — correct. When k >= s.length, the window can always swallow the whole string (you can replace everything), so best reaches s.length naturally; no clamp needed.left index that produced the best width: whenever you update best, also store bestLeft = left. At the end, s.slice(bestLeft, bestLeft + best) is one valid window — pick any letter that hits maxFreq inside it as the replacement target. There can be several tied-longest substrings; this returns the earliest.maxFreq optimization, stated precisely. We can leave maxFreq stale because the answer is monotone in maxFreq: a larger maxFreq only ever permits longer windows. Since best records the maximum window length over the whole scan, and a window of length L was first achieved when maxFreq was its true value at that moment, no later stale value can produce a longer valid window than one that was genuinely valid. If you ever needed the exact answer for a single fixed window rather than the running maximum, you would have to recompute maxFreq honestly — the shortcut is specific to this "longest over all windows" framing.Map keyed by whatever characters (or code points, or tokens) appear, and the same logic works for lowercase, Unicode, or arbitrary symbol streams. The only thing that changes is the cost of a hypothetical maxFreq recompute — which, per the previous point, you don't do anyway.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're given a string s and a budget k. You may replace at most k characters in s with any other letters. After those replacements, what is the length of the longest run of a single repeated character you can produce? You don't have to return the substring itself — just its length. Think of it as a contiguous stretch of the string where, by spending up to k swaps, every character becomes the same letter.
// s: string — the input (assume uppercase A–Z letters)
// k: number — the maximum number of characters you may replace (k >= 0)
// returns: number — the length of the longest substring that becomes
// a single repeated character after at most k replacements
function longestRepeatingSubstringAfterReplacements(s, k): number;The substring must be contiguous — you pick a start and end index, and within that window you replace up to k characters so the whole window is one letter.
// Replace both 'B's with 'A' (or both 'A's with 'B') → "AAAA" or "BBBB", length 4.
longestRepeatingSubstringAfterReplacements('ABAB', 2); // → 4// Window "BABB" (indices 2–5): replace the one 'A' at index 3 with 'B' to get
// "BBBB" using one swap. Length 4. No valid window of length 5 exists for k=1.
longestRepeatingSubstringAfterReplacements('AABABBA', 1); // → 4// With no replacements allowed, you can only use a run that already exists.
// The longest existing run of one character is "BBB", length 3.
longestRepeatingSubstringAfterReplacements('AABBBCC', 0); // → 3// Every character is already the same — no swaps needed, the whole string counts.
longestRepeatingSubstringAfterReplacements('BBBBBB', 2); // → 6A–Z. You don't need to handle lowercase, digits, or other characters — though the sliding-window approach generalizes to any alphabet (see the solution's Going further).k replacements, not exactly k. If a window is already uniform you spend zero swaps; you never have to use the full budget.k can be 0. With no swaps allowed, the answer is the longest run of a single repeated character that already exists in s.0. No window, no length.k may exceed the string length. If your budget is at least the length of s, you can turn the entire string into one letter — the answer is s.length.You'll find the length of the longest contiguous stretch of s that can become a single repeated letter after replacing at most k characters — using a window that slides across the string exactly once.
You have a string and a budget of k swaps. Within some contiguous window, you want every character to end up the same letter. The cheapest way to make a window uniform is to keep whichever letter already appears most often inside it and replace all the others. So the number of swaps a window costs is its length minus the count of its most-common letter. If that cost fits in your budget k, the window is achievable. Your job is to find the longest such window.
Concretely: in the window "BABB", B appears 3 times and A once. To make it all B, you replace the single A — one swap. With k = 1, that window is achievable, so it contributes a length of 4 to your answer.
Track a window with two pointers, left and right. Inside it, keep a count of each character and the largest of those counts — call it maxFreq. The characters you'd have to replace to make the window uniform is windowLength - maxFreq. A window is valid when that number is at most k.
The whole algorithm is: push right forward one character at a time, growing the window; whenever the window becomes invalid, pull left forward to shrink it back; the answer is the largest valid window length you ever see.
The obvious move is to check every possible substring. For each start index i and each end index j, count the characters in s[i..j], find the most common one, and see whether the rest fit in k.
function brute(s, k) {
let best = 0;
for (let i = 0; i < s.length; i++) {
const count = {};
let maxFreq = 0;
for (let j = i; j < s.length; j++) {
count[s[j]] = (count[s[j]] || 0) + 1;
maxFreq = Math.max(maxFreq, count[s[j]]);
const len = j - i + 1;
if (len - maxFreq <= k) best = Math.max(best, len); // window achievable?
}
}
return best;
}This is correct — it literally considers every window. But it's O(n²): there are about n²/2 substrings, and even though we reuse the count map as j grows (so we don't recount from scratch within one i), the outer loop restarts that map for every new i. On a 10,000-character string that's ~50 million iterations. The waste is that each new starting index throws away everything we learned about overlapping windows and recounts the same characters again.
Instead of restarting for every start index, keep one window and move both edges forward only. Each character enters the window once (when right passes it) and leaves at most once (when left passes it), so the whole scan is O(n).
function longestRepeatingSubstringAfterReplacements(s, k) {
const count = {}; // count[c] = occurrences of c in the current window
let left = 0; // left edge of the window
let maxFreq = 0; // largest single-character count seen in any window so far
let best = 0; // longest valid window length found
for (let right = 0; right < s.length; right++) {
const c = s[right];
count[c] = (count[c] || 0) + 1; // the new char enters the window
maxFreq = Math.max(maxFreq, count[c]); // it may be the new most-common char
// windowLength - maxFreq is the number of chars we'd replace.
// If that exceeds k, the window is invalid: drop the leftmost char.
if ((right - left + 1) - maxFreq > k) {
count[s[left]]--;
left++;
}
// After the (at most one) shrink, the window [left..right] is valid.
best = Math.max(best, right - left + 1);
}
return best;
}
module.exports = { longestRepeatingSubstringAfterReplacements };A few choices here are worth pausing on.
Why if and not while for the shrink. The window grows by exactly one character per iteration, so it can become invalid by at most one over-budget character at a time. A single left++ per step is enough to keep pace — we never need to shrink twice in one iteration. This also means left advances at most n times total across the whole run, which is what keeps the algorithm linear. A while loop here would also be correct, but the if makes the "window never shrinks below the best" behaviour explicit (more on that in the gotchas).
Why maxFreq is never decreased, even when left moves past the most-common character. This is the subtle part. When we shrink, we decrement count[s[left]], but we do not recompute maxFreq. It can therefore be momentarily larger than the true maximum count in the current window. That looks like a bug, but it's deliberate and safe — explained in full in the walkthrough and gotchas below. The short version: a stale-high maxFreq only ever lets the window keep its current width; it can never produce a window wider than one that was genuinely valid earlier, so best is never inflated.
Why best = Math.max(best, ...) every iteration. Writing best = right - left + 1 directly would be wrong on the rare step where the window held flat — taking the max is the safe, clear way to record the widest window seen, and on a growing step it captures the new width immediately.
Let's trace s = "AABABBA", k = 1. Notation: the window is [left..right] inclusive.
right=0 c='A' count={A:1} maxFreq=1
len 1 - 1 = 0 <= 1 valid window "A" best=1
right=1 c='A' count={A:2} maxFreq=2
len 2 - 2 = 0 <= 1 valid window "AA" best=2
right=2 c='B' count={A:2,B:1} maxFreq=2
len 3 - 2 = 1 <= 1 valid window "AAB" best=3
right=3 c='A' count={A:3,B:1} maxFreq=3
len 4 - 3 = 1 <= 1 valid window "AABA" best=4
right=4 c='B' count={A:3,B:2} maxFreq=3
len 5 - 3 = 2 > 1 INVALID
drop s[left]=s[0]='A': count={A:2,B:2}, left=1
window "ABAB" (len 4) best=4
right=5 c='B' count={A:2,B:3} maxFreq=3
len 5 - 3 = 2 > 1 INVALID
drop s[left]=s[1]='A': count={A:1,B:3}, left=2
window "BABB" (len 4) best=4
right=6 c='A' count={A:2,B:3} maxFreq=3
len 5 - 3 = 2 > 1 INVALID
drop s[left]=s[2]='B': count={A:2,B:2}, left=3
window "ABBA" (len 4) best=4
return 4
Now look at the steps after right=3. Once maxFreq reached 3 (at right=3, the three As in "AABA"), it never goes back down — even at right=6 where the window "ABBA" has a true max count of only 2. At right=6, maxFreq is stale: it's still 3 from a window that no longer exists.
Why doesn't that break anything? Once the window reached width 5 and was invalid (at right=4), we shrink by one and the window stays width 4 from then on. A stale-high maxFreq makes the validity check easier to pass, so the window holds its width but never grows wider than it was. And the only width that matters for the answer is the widest valid window we ever found — recorded back at right=3 when maxFreq was honestly 3. The stale value can't manufacture a window wider than a genuinely valid one: best only increases when right - left + 1 exceeds the previous best, which requires the window to actually grow past its old width. The first time any width L was reached, maxFreq was a real count; and maxFreq can only rise from there, so a stale value never unlocks a new, larger width that wasn't already legitimately reachable.
windowLength - maxFreq <= k, not anything involving the second-most-common count. The chars you replace are everything that isn't the most-common letter: windowLength - maxFreq. If that's within budget k, you can make the window uniform. Get this expression wrong and every answer is off.maxFreq does not need to be perfectly accurate after a shrink — and recomputing it would cost performance for zero correctness gain. You might be tempted to scan all counts to refresh maxFreq whenever left moves. It's unnecessary: a stale-high maxFreq only lets the window keep its width, never exceed the best already recorded. Recomputing it on every shrink would add an O(alphabet) factor for no benefit. Leave it alone.k = 0 is the "longest existing run" problem. With no swaps, windowLength - maxFreq <= 0 forces windowLength === maxFreq, i.e. every character in the window is the same. The algorithm degrades gracefully into "find the longest run of one repeated character" — no special-casing needed.count[s[right]] when a character enters and decrement count[s[left]] when one leaves. Forget the decrement and the counts drift upward, maxFreq inflates without bound, the window never effectively shrinks, and you'll return numbers larger than the string.if removes at most one, the window's width is monotonically non-decreasing: it stays flat on an invalid step or grows on a valid one, but it never gets smaller. That's why a single if suffices and why left advances at most n times total.s never enters the loop, so best stays 0 — correct. When k >= s.length, the window can always swallow the whole string (you can replace everything), so best reaches s.length naturally; no clamp needed.left index that produced the best width: whenever you update best, also store bestLeft = left. At the end, s.slice(bestLeft, bestLeft + best) is one valid window — pick any letter that hits maxFreq inside it as the replacement target. There can be several tied-longest substrings; this returns the earliest.maxFreq optimization, stated precisely. We can leave maxFreq stale because the answer is monotone in maxFreq: a larger maxFreq only ever permits longer windows. Since best records the maximum window length over the whole scan, and a window of length L was first achieved when maxFreq was its true value at that moment, no later stale value can produce a longer valid window than one that was genuinely valid. If you ever needed the exact answer for a single fixed window rather than the running maximum, you would have to recompute maxFreq honestly — the shortcut is specific to this "longest over all windows" framing.Map keyed by whatever characters (or code points, or tokens) appear, and the same logic works for lowercase, Unicode, or arbitrary symbol streams. The only thing that changes is the cost of a hypothetical maxFreq recompute — which, per the previous point, you don't do anyway.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.