Coding · Sliding window
Longest Repeating Character Replacement
- Appears on company lists
- Medium
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
Given a string s of uppercase letters and an integer k, you may change any character to any other uppercase letter at most k times in total. Return the length of the longest substring that can be made of one repeated letter. For s = "AABABBA" and k = 1 the answer is 4, for example by turning the single B in "AABA" into an A. The string can have up to 100,000 characters, so checking every substring is too slow.
Restated in our own words, not a quote from Microsoft or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I ask whether the alphabet is only uppercase letters, because that lets me use an array of 26 counters instead of a map. Then I ask how long the string can be, whether k can be zero or larger than the string, and what to return for an empty string. I also confirm that one change turns a character into any other letter, and that only the length is wanted, not the substring itself.
Assumptions: letters A to Z only, length up to 100,000, k between 0 and the length, an empty string returns 0, and the answer is a number. Because of the length I aim for one linear pass with a fixed amount of extra memory.
Brute force
Say the obvious answer and why it is too slow.
The direct approach tries every substring. For each start and end I count the letters inside, find the most frequent one, and check whether the other letters number at most k, that is, whether length minus the highest count is at most k. Counting from scratch for each pair costs O(n) per substring, and there are O(n²) substrings, so O(n³) in total. Keeping the counts while the end moves right brings it to O(n²), or O(26·n²) if the maximum is rescanned each time. At n = 100,000 that is about five billion pair checks even in the good case, far too slow. The waste is that neighbouring substrings share almost all of their letters, and validity has a monotone shape: shrinking a valid window never breaks it. That is exactly what a sliding window exploits.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(1) extra
A substring can be turned into one repeated letter with at most k edits exactly when its length minus the count of its most frequent letter is at most k. I keep the most common letter and rewrite everything else. So the task becomes: find the longest window where size - maxCount <= k. This is a variable-size sliding window, and the monotone validity is what makes two pointers legal.
There is a tidy version in which the window never shrinks. For each new right end I count the letter and update maxCount, the highest single-letter count seen in any window so far. If the window is still valid I keep it. If not, I move the left end one step, so the window slides along at the same length instead of shrinking.
Why is a stale maxCount safe? When a letter leaves the window I do not reduce maxCount, so it may be larger than the true maximum of the current window. The window length never exceeds maxCount + k, and maxCount only rises when some letter truly reaches that count inside the current window. So the final length is always one that a real valid window reached, and a longer answer would need a higher real count. A stale value can never make the reported length bigger than the truth.
Out loud: the window is as long as the best answer so far. It grows when a better letter count appears and otherwise slides along. The answer is the final window length, which is s.length - left.
Walk it through
A dry run on the example, step by step.
| right | char | counts | maxCount | window | size |
|---|---|---|---|---|---|
| 0 | A | A1 | 1 | [0,0] | 1 |
| 1 | A | A2 | 2 | [0,1] | 2 |
| 2 | B | A2 B1 | 2 | [0,2] | 3 |
| 3 | A | A3 B1 | 3 | [0,3] | 4 |
| 4 | B | A3 B2, drop A: A2 B2 | 3 | [1,4] | 4 |
| 5 | B | A2 B3, drop A: A1 B3 | 3 | [2,5] | 4 |
| 6 | A | A2 B3, drop B: A2 B2 | 3 | [3,6] | 4 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Run s = AABABBA with k = 1 and follow the trace. The first four letters fit: after A, A, B, A the window is [0,3] with size 4 and A counted three times, so one edit covers the single B. The B at index 4 makes the size 5 while the best count is still 3, so 5 - 3 = 2 exceeds k, and the left end moves to 1, dropping an A. The window keeps its length of 4 and slides. At index 5 another B arrives; its count of 3 ties the old maxCount without beating it, so the window slides again. At index 6 an A cannot lift anything, and the window slides once more. The left end finishes at 3, so the answer is 7 - 3 = 4. The maxCount column never goes past 3, which is why the length stays at 4.
The code
Runnable JavaScript, checked against test cases.
function characterReplacement(s, k) {
const counts = new Array(26).fill(0);
const base = "A".charCodeAt(0);
let left = 0;
let maxCount = 0;
for (let right = 0; right < s.length; right++) {
const added = s.charCodeAt(right) - base;
counts[added]++;
maxCount = Math.max(maxCount, counts[added]);
if (right - left + 1 - maxCount > k) {
counts[s.charCodeAt(left) - base]--;
left++;
}
}
return s.length - left;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Empty string: the loop never runs and
s.length - leftis 0. - k = 0: the window slides whenever a different letter arrives, so the answer is the longest run of equal letters.
- k at least the length: the window never slides and the answer is the whole length.
- All the same letter: maxCount tracks the window size, nothing slides, and the answer is n.
- All different letters: maxCount stays at 1, so the answer is the smaller of n and k + 1.
- Memory: the counters are a fixed 26-slot array, so memory does not depend on the length of the string.
Follow-ups to expect
Where the interviewer pushes next.
- Can you do it with a while loop that shrinks the window, and why would that be easier to prove?
- What changes if the alphabet is all Unicode characters instead of 26 letters?
- How would you return the substring itself, not only its length?
- How does this relate to the problem of the longest run of ones after flipping at most k zeros?
- How would you handle a stream of characters where the string is too large to hold in memory?
Where candidates slip
The mistakes this problem punishes.
- Writing the validity test with the wrong comparison, such as
>= kor< k, instead of> k. - Forgetting to decrement the count of the letter at
leftbefore moving the left end. - Trying to keep
maxCountexact by subtracting one when a letter leaves. That is wrong, because a different letter may now hold the maximum. - Leaving maxCount stale without being able to explain why that is safe, which is the usual follow-up question.
- Scanning all 26 counters on every step to find the maximum. That is still linear, but you should say it is 26n and not n.
- Assuming the replacement letter must already appear in the string.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.