You are given a string s and an integer k. You may choose any character of s and change it to any other uppercase English letter; you can perform this operation at most k times.
Return the length of the longest substring that, after at most k such replacements, contains only one distinct character.
Example
Replace the two "A"s with "B"s (or vice versa) to get "BBBB" — length 4.
Constraints
- 1 <= s.length <= 10^5
sconsists of uppercase English letters.- 0 <= k <= s.length
Intuition
We may rewrite up to k characters; we want the longest run we can turn into a single repeated letter. The most direct approach tries every substring and asks whether it can be made uniform: keep the most common letter in it and replace the rest, which is feasible when the count of other letters is <= k.
function characterReplacement(s, k) {
let best = 0;
// Try every substring s[i..j].
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
// Count letters in this substring to find the most frequent one.
const count = {};
let maxFreq = 0;
for (let m = i; m <= j; m++) {
count[s[m]] = (count[s[m]] ?? 0) + 1;
maxFreq = Math.max(maxFreq, count[s[m]]);
}
const len = j - i + 1;
// Replaceable when the non-dominant letters fit within the k budget.
if (len - maxFreq <= k) best = Math.max(best, len);
}
}
return best;
}Re-counting every substring is O(n³). Can we do better?
The replaceability test for a window is windowLength - maxFreq <= k, where maxFreq is the count of its most frequent letter. That's a property of a contiguous run — so use a sliding window and maintain the letter counts incrementally as the edges move, instead of rebuilding them.
Grow right each step. When windowLength - maxFreq > k the window is too costly to make uniform, so advance left by one — and that's the elegant part: we never need to shrink more than one step, because we only care about the largest window ever seen. The width is monotonically non-decreasing, so the final right - left + 1 is the answer. (We let maxFreq go stale when left moves; a bigger answer would require an even bigger maxFreq, so this never overcounts.)
Walking it through:
s = "AABABBA", k = 1 — grow right; left nudges forward when cost > k
"AAB": replace the single B → all A. Cost 1 fits the budget.
"AABA": three A's, one B to replace. Still within k = 1. best grows to 4.
"AABAB": now two B's must change — over budget. Slide left one step.
Window width holds at 4 (left moved once, right once). best stays 4.
left kept pace with right, holding width 4 (maxFreq is the stale 3, which never overcounts). Final best = 4.
Optimization
Sliding window with most-frequent count
A window [left, right] can be made uniform with at most k replacements when the number of characters that aren't the window's most-frequent character is <= k — i.e. windowLength - maxFreq <= k, where maxFreq is the highest single-letter count inside the window.
Grow right one step at a time, updating the count of the entering letter and maxFreq. Whenever windowLength - maxFreq > k the window can no longer be made uniform, so slide left forward by one (dropping a letter). Crucially the window never needs to shrink below its best width: because left only ever advances when forced, the window width is monotonically non-decreasing, and its final width is the answer.
maxFreq is allowed to be stale (we never decrease it when left moves); that's fine, because a larger answer can only come from a window with an even larger maxFreq, so the recorded width never overcounts.
O(s.length) time, O(1) space (26-letter alphabet).
function characterReplacement(s, k) {
const A = 'A'.charCodeAt(0);
// count[c]: occurrences of letter c inside the current window.
const count = new Array(26).fill(0);
let left = 0;
let maxFreq = 0; // highest single-letter count seen in any window so far
let best = 0;
for (let right = 0; right < s.length; right++) {
const enter = s.charCodeAt(right) - A;
count[enter]++;
// The dominant letter is the cheapest to keep; everything else must be replaced.
maxFreq = Math.max(maxFreq, count[enter]);
// If the non-dominant characters exceed k, this window can't be made uniform.
while (right - left + 1 - maxFreq > k) {
count[s.charCodeAt(left) - A]--;
left++;
}
// The window is valid here; its width is a candidate answer.
best = Math.max(best, right - left + 1);
}
return best;
}Complexity analysis
Time complexity: O(n). Here's why:
rightadvances across the string once;leftonly ever moves forward and at most as far asright.- Each step does O(1) work — one count update, a
maxFreqcomparison, and at most one left eviction (the alphabet is a fixed 26 letters, somaxFreqis read directly, never re-scanned).
Both pointers traverse the string at most once, so the whole pass is O(n) where n = s.length.
Space complexity: O(1). Here's why:
- The
countarray has a fixed 26 slots, one per uppercase letter. - A handful of integers (
left,maxFreq,best) round it out.
Independent of input size, the extra space is O(1).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| s = "B", k = 0 | 1 | Single character — already uniform. |
| s = "CCCC", k = 0 | 4 | All same with no budget — the whole string. |
| s = "XYZW", k = 0 | 1 | All distinct, no replacements — best run is a single letter. |
| s = "XYXY", k = 2 | 4 | Budget covers the two minority letters — whole string becomes uniform. |
| s = "AABBA", k = 1 | 3 | k = 1 can't unify all five; the best window is width 3. |
| s = "AAABBB", k = 2 | 5 | k = 2 stretches across the boundary for a width-5 window. |
Try it yourself
Write your solution against the real judge before checking the reference.