Longest Repeating Character Replacement
The Prompt
You are given a string `s` and an integer `k`. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most `k` times. Return the length of the longest substring containing the same letter you can get after performing the above operations.
Understanding the Problem
You may repaint at most k characters, and you want the longest window that can become all one letter. Flip the question around: a window of length L works exactly when L − (count of its most frequent letter) ≤ k — keep the majority letter, repaint everyone else.
So instead of trying replacements, slide a window and track character frequencies. The window is valid while (window length) − maxFreq ≤ k; when it goes over, shrink from the left.
The Interview Flow
Interviewer
Given a string and an integer k, find the length of the longest substring with all same characters, if you can replace at most k characters.
Candidate
This seems like a sliding window problem. The window would represent my current substring. I need to know if the substring is "valid".
Interviewer
How do you define a "valid" window?
Candidate
A window is valid if the number of characters I need to replace to make them all the same is less than or equal to k. The number of replacements needed is `window.length - count_of_most_frequent_character`.
Interviewer
That's the core logic. How do you implement this with a sliding window?
Candidate
I'll use two pointers, `left` and `right`, to define the window. I'll expand the window by moving `right`. As I do, I'll keep a frequency map of characters within the window and track the count of the most frequent character. I check the condition: `(right - left + 1) - max_frequency <= k`. If this condition is violated, the window is invalid, and I must shrink it by moving the `left` pointer and updating my frequency map. At each valid step, I update my result with the current window size.
Interviewer
That's a perfect O(n) approach. Please code it.
Why can maxFreq be stale and the answer still be right?
The invariant: the window size only grows when the current window genuinely satisfies length − maxFreq ≤ k. The classic trick is that maxFreq is never decremented on shrink — it may overstate the current window. That only makes the validity check lenient, and a lenient check merely lets the window coast at its best-ever size; it records a new maxLength only after a real, higher maxFreq re-validates a bigger window.
Each pointer moves forward at most n times and the frequency map has at most 26 keys, so the whole thing is O(n) time, O(1) space — versus O(n²) for testing every window from scratch.
O(n) Sliding Window Solution
- Initialize `left = 0`, `maxLength = 0`, `maxFreq = 0`, and a frequency map for characters.
- Iterate through the string with a `right` pointer.
- Increment the count of the character `s[right]` in the frequency map.
- Update `maxFreq` to be the maximum frequency of any character seen in the current window so far.
- Check if the current window is invalid: `(right - left + 1) - maxFreq > k`.
- If it is invalid, shrink the window from the left: decrement the count of `s[left]` and increment `left`.
- Update `maxLength` with the size of the current valid window: `maxLength = max(maxLength, right - left + 1)`.
- Return `maxLength` after the loop.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function characterReplacement(s, k) {
let left = 0, maxLength = 0, maxFreq = 0;
const freqMap = {};
for (let right = 0; right < s.length; right++) {
const char = s[right];
freqMap[char] = (freqMap[char] || 0) + 1;
maxFreq = Math.max(maxFreq, freqMap[char]);
if ((right - left + 1) - maxFreq > k) {
freqMap[s[left]]--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}Explanation
Run s = "AABABBA" with k = 1 — the answer is 4.
1Window "AABA": counts are A = 3, B = 1, so maxFreq = 3. Check: 4 − 3 = 1 ≤ k. Repaint the one B → "AAAA". maxLength = 4.
2r = 4 adds another B: window size 5, maxFreq still 3, and 5 − 3 = 2 > k. Invalid — drop s[0] = A and move l to 1. The window coasts at size 4.
3The pattern repeats: every time size hits 5 the check 5 − 3 = 2 > k shrinks it back to 4. Nothing ever beats 4 — the answer.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.