Longest Repeating Character Replacement
Problem Statement
Given a string s containing only uppercase English letters and an integer k, return the length of the longest substring that can be transformed into a substring with the same repeated character by replacing at most k characters.
Input
A string s of uppercase letters and an integer k, the maximum number of replacements allowed.
Output
An integer: the maximum length of a contiguous substring that can become all one character using at most k replacements.
Constraints
- •
1 <= s.length <= 10^5 - •
s consists of only uppercase English letters - •
0 <= k <= s.length
Examples
Example 1
s = ABAB, k = 2
4Example 2
s = AABABBA, k = 1
4Example 3
s = AAAA, k = 0
4Learning Objectives
- Translate replacement budget into the validity test **window length - max frequency <= k**.
- Maintain frequency counts while expanding and shrinking a variable window.
- Understand why the tracked maximum frequency does not need to decrease during shrinking.
- Use the longest-valid template without checking every target character separately.
Intuition
Pattern Identification
This is a longest-valid variable-window problem. For any fixed window, the best target character is the character that already appears most often. Every other character must be replaced, so the window is valid exactly when window length - max frequency in window <= k.
The expand and shrink invariant is budget feasibility. Expand right to try a larger answer. If the number of needed replacements exceeds k, shrink left until the window size is no longer beyond what the current best frequency can support. The subtle greedy insight is that max frequency can be kept as the largest value ever seen while expanding; an overestimated value may delay shrinking, but it never causes the final best length to exceed a length that was supported when that maximum frequency was achieved.
Common mistakes
- ×Counting replacements against the first character in the window instead of the most frequent character.
- ×Recomputing the maximum frequency from scratch on every shrink for no benefit.
- ×Shrinking when **window length - max frequency == k** even though the window is still valid.
- ×Trying all 26 target letters separately when one frequency table is enough.
Algorithm Explanation
Window setup
Keep left, right, a frequency table for the 26 uppercase letters, and maxFrequency, the largest count of any letter observed in the current expansion history. A window of length L is valid when L - maxFrequency <= k.
Window visualization
For s = AABABBA and k = 1, the window grows through AABA. Its length is 4 and the highest frequency is 3 for A, so only one replacement is needed and best = 4. When right reaches the next B, the window AABAB has length 5 and max frequency 3, so it would need 2 replacements. Shrink left once to keep the search focused on windows that can match the current budget.
Algorithm
- Initialise left = 0, best = 0, maxFrequency = 0, and a 26-entry frequency table.
- For each right, add s[right] to the table and update maxFrequency.
- If right - left + 1 - maxFrequency > k, remove s[left] and increment left.
- Update best with the current window length.
- Return best after the scan.
Solutions
Solution: Frequency window with replacement budget
The frequency table tells us the cheapest character to make the whole window equal to: keep the majority letter and replace the rest. The window only shrinks when the number of non-majority characters exceeds k.
Step-by-step
- Count letters as the right boundary expands.
- Keep maxFrequency as the largest count reached by any letter during expansion.
- When the window would need more than k replacements, remove the leftmost letter and move left forward.
- Record the largest window length seen after the budget check.
- Return that length.
O(n)
O(1)
The scan is linear and the frequency table always has 26 entries.
Java implementation
Dry Run
Sample input
s = AABABBA, k = 1. Track the window length, the best majority count, replacements needed, and the best answer.
| step | right char | left | window | maxFrequency | needed replacements | best |
|---|---|---|---|---|---|---|
| 1 | A at 0 | 0 | A | 1 | 0 | 1 |
| 2 | A at 1 | 0 | AA | 2 | 0 | 2 |
| 3 | B at 2 | 0 | AAB | 2 | 1 | 3 |
| 4 | A at 3 | 0 | AABA | 3 | 1 | 4 |
| 5 | B at 4 | 1 | ABAB | 3 | 1 after shrinking | 4 |
| 6 | B at 5 | 2 | BABB | 3 | 1 after shrinking | 4 |
| 7 | A at 6 | 3 | ABBA | 3 | 1 after shrinking | 4 |
The longest valid window length is 4. The table keeps maxFrequency = 3, which is enough to preserve the correct best length.
Interview Tips
Lead with the formula window length - max frequency because it explains the whole problem. Be ready to justify stale maxFrequency: it may make the current window look better than it is, but the answer length was achievable when that frequency was originally present, and the window only grows one step at a time.
Likely follow-ups
- What if the alphabet were much larger than 26 characters?
- How would you return the substring bounds as well as the length?
- How would the solution change if different characters had different replacement costs?
- How would you solve the binary version where you may flip at most **k** zeroes?
Similar Problems
Key Takeaways
- The best replacement target inside a window is its most frequent character.
- A window is valid when non-majority characters fit inside the replacement budget.
- For this longest-window problem, **maxFrequency** does not need to decrease while shrinking.
- Shrink only when the budget is exceeded, not when it is exactly used.