Longest Repeating Character Replacement
Replace characters to get the longest repeating character substring.
Examples
Both changes can go to the same letter: flip the two 'A's to get "BBBB", or the two 'B's to get "AAAA".
With one change, turn the middle 'A' into 'B': "AABBBBA" now holds the run "BBBB", 4 letters long.
Problem Understanding
The input is an uppercase string s and a budget k. One operation overwrites a single character with any other uppercase letter, and you may spend up to k operations.
Goal: return the length of the longest substring that can be made entirely of one repeated letter within that budget.
Algorithm Strategy
We use a Sliding Window to check if a valid window exists. A window (substring) is valid if we can turn it into all same characters using at most k replacements.
Logic:
- Validity Check:
Replacements Needed = Window Length - Count of Most Frequent Char.- If
Replacements Needed <= k, the window is valid. We try to expand it (incrementright). - If
Replacements Needed > k, the window involves too many changes. We perform one shrink step (incrementleft) to try and make it valid again.
- If
- We maintain a frequency map (or array of size 26) to track counts of characters in the current window.
- We keep track of
max_count, the highest count any character has reached in a window so far. It is never decreased, which is why the map is never re-scanned; the section below explains why a stale value still gives the right answer.
Interactive Visualization
Watch how the window expands and only shrinks when the number of replacements needed exceeds k.
Dry Run: s = "AABABBA", k = 1
Each row is one step of the loop: add s[right], update maxCount, and if the window needs more than k replacements, drop one character from the left.
| right | Char | Counts | maxCount | Length | Needed | Action | Best |
|---|---|---|---|---|---|---|---|
| 0 | A | A:1 |
1 | 1 | 0 | keep | 1 |
| 1 | A | A:2 |
2 | 2 | 0 | keep | 2 |
| 2 | B | A:2, B:1 |
2 | 3 | 1 | keep (1 ≤ k) | 3 |
| 3 | A | A:3, B:1 |
3 | 4 | 1 | keep | 4 |
| 4 | B | A:3, B:2 |
3 | 5 | 2 | drop A at 0, left = 1 | 4 |
| 5 | B | A:2, B:3 |
3 | 5 | 2 | drop A at 1, left = 2 | 4 |
| 6 | A | A:2, B:3 |
3 | 5 | 2 | drop B at 2, left = 3 | 4 |
Once the window reaches length 4 it never shrinks: every later step adds one character and, when that breaks the rule, drops one. Result: 4.
Edge Cases & Common Mistakes
Edge Cases:
- k = 0: You can't replace anything. The problem becomes finding the longest existing substring of same chars.
- String no longer than k: If the string has at most
kcharacters, every character can be replaced, so the answer is the string length. - All Same Chars: Answer is string length.
Common Mistakes:
- Re-calculating Max Freq: You don't need to decrement
max_countwhen shrinking the window. Even if the actual max frequency drops, we only care about finding a larger window, so a historically highmax_countacts as a threshold. (This is a subtle optimization). - Map Size: Remember to use
ord(char) - ord('A')for array indexing.
Solution
O(N) solution using Sliding Window and Frequency Array.
Longest Repeating Character Replacement Code
1var characterReplacement = function(s, k) {2 const count = new Array(26).fill(0);3 let maxCount = 0;4 let left = 0;5 let maxLen = 0;6 const base = 'A'.charCodeAt(0);78 for (let right = 0; right < s.length; right++) {9 const index = s.charCodeAt(right) - base;10 count[index]++;11 maxCount = Math.max(maxCount, count[index]);1213 if ((right - left + 1) - maxCount > k) {14 const leftIndex = s.charCodeAt(left) - base;15 count[leftIndex]--;16 left++;17 }18 maxLen = Math.max(maxLen, right - left + 1);19 }20 return maxLen;21};
More practice: DSA interview questions with answers · patterns cheat sheet