Longest Repeating Character Replacement
Problem
Given a string s and an integer k, return the length of the longest substring containing the same letter you can get after performing at most k character replacements.
- 1 ≤ s.length ≤ 10⁵
- s consists of only uppercase English letters.
- 0 ≤ k ≤ s.length
Example
s = "ABAB", k = 24The entire string "ABAB" can be transformed into "AAAA" or "BBBB" by replacing the two 'B's or two 'A's respectively. The algorithm uses a sliding window to track the frequency of characters in the current window and the count of the most frequent character. When the window size minus the max frequency exceeds k, it shrinks the window from the left. This ensures the window always represents a valid substring where at most k replacements are needed. The maximum window size encountered during this process is 4.
Approach
Straightforward Solution
A brute-force approach would check every substring, count character frequencies, and verify if replacements needed are within k. This leads to O(n^2) time complexity, which is too slow for large inputs.
Core Observation
The length of the longest valid substring depends on the count of the most frequent character within the window. The difference between the window size and this max frequency represents the minimum replacements needed to make all characters identical.
Path to Optimal
PreviewRecognizing that the problem can be solved with a sliding window that expands and contracts based on the replacement constraint is key…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a sliding window with two pointers. Expand the right pointer, update character counts and max frequency…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each character is visited at most twice: once when the right pointer expands the window and once when the left pointer shrinks it, resulting in linear time complexity.
Space
O(1)
The counts dictionary stores frequencies of uppercase English letters only, which is a fixed size of 26, resulting in constant auxiliary space.
Pattern Spotlight
Sliding Window (Variable Size with Frequency Tracking)
Maintain a window that represents a valid substring by tracking the count of the most frequent character; if the window size minus this count exceeds k, shrink the window from the left to restore validity.
Solution
| 1 | class Solution:
|
| 2 | def characterReplacement(self, s: str, k: int) -> int:
|
| 3 | counts = {}
|
| 4 | left = 0
|
| 5 | max_freq = 0
|
| 6 | max_length = 0
|
| 7 |
|
| 8 | for right in range(len(s)):
|
| 9 | char = s[right]
|
| 10 | counts[char] = 1 + counts.get(char, 0)
|
| 11 | max_freq = max(max_freq, counts[char])
|
| 12 |
|
| 13 | while (right - left + 1) - max_freq > k:
|
| 14 | counts[s[left]] -= 1
|
| 15 | left += 1
|
| 16 |
|
| 17 | max_length = max(max_length, right - left + 1)
|
| 18 |
|
| 19 | return max_length |
Step-by-Step Solution
Initialize Sliding Window State and Frequency Tracking
| 3 | counts = {}
|
| 4 | left = 0
|
| 5 | max_freq = 0
|
| 6 | max_length = 0
|
Objective
To set up the data structures and variables needed to track character frequencies, window boundaries, and the maximum substring length.
Key Insight
Initializing a frequency dictionary and pointers for the sliding window allows the algorithm to dynamically track the composition of the current substring. Maintaining max_freq separately avoids recomputing the maximum frequency in the window on every iteration, enabling efficient window validation.
Interview Quick-Check
Core Logic
The counts dictionary tracks frequencies of characters in the current window, while max_freq stores the highest frequency to quickly check window validity.
State & Boundaries
Left pointer starts at 0, representing the start of the sliding window.
Common Pitfalls & Bugs
Forgetting to initialize max_freq to 0 can lead to incorrect window size calculations.
Expand Window and Update Frequencies While Maintaining Validity
To iterate through the string with the right pointer, update character counts and max frequency, and shrink the window when replacements exceed k.
Track and Return the Maximum Valid Substring Length
To update the maximum length of a valid substring found so far and return it after processing the entire string.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
max_freq = 0Initialize max_freq to track the highest frequency of any character in the current window.
Maintaining max_freq allows efficient validation of the window without scanning all counts repeatedly, which is critical for performance.
max_freq = max(max_freq, counts[char])Update max_freq to the highest frequency seen in the current window.
Keeping max_freq updated allows quick checks of how many replacements are needed without scanning all counts, which is vital for efficiency.
while (right - left + 1) - max_freq > k:Check if the window size minus max_freq exceeds k, indicating too many replacements are needed.
This condition detects when the current window is invalid under the replacement constraint, triggering window shrinking.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does the algorithm track the count of the most frequent character in the current window instead of the counts of all characters?
See the answer with Pro.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Longest Repeating Character Replacement from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Repeating Character Replacement drill