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
Recognizing that the problem can be solved with a sliding window that expands and contracts based on the replacement constraint is key. By maintaining counts of characters and tracking the max frequency in the current window, the algorithm can efficiently determine when to shrink the window. This transforms the problem into a linear time solution.
Optimal Approach
Use a sliding window with two pointers. Expand the right pointer, update character counts and max frequency. If the window size minus max frequency exceeds k, move the left pointer to shrink the window and update counts accordingly. Track the maximum window size throughout. This approach guarantees O(n) time and O(1) space since the character set is fixed.
Time
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 |
| 1 | class Solution { |
| 2 | public int characterReplacement(String s, int k) { |
| 3 | int[] counts = new int[26]; |
| 4 | int left = 0; |
| 5 | int maxFreq = 0; |
| 6 | int maxLength = 0; |
| 7 | |
| 8 | for (int right = 0; right < s.length(); right++) { |
| 9 | int index = s.charAt(right) - 'A'; |
| 10 | counts[index]++; |
| 11 | maxFreq = Math.max(maxFreq, counts[index]); |
| 12 | |
| 13 | while ((right - left + 1) - maxFreq > k) { |
| 14 | counts[s.charAt(left) - 'A']--; |
| 15 | left++; |
| 16 | } |
| 17 | |
| 18 | maxLength = Math.max(maxLength, right - left + 1); |
| 19 | } |
| 20 | |
| 21 | return maxLength; |
| 22 | } |
| 23 | } |
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
| 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])
|
| 13 | while (right - left + 1) - max_freq > k:
|
| 14 | counts[s[left]] -= 1
|
| 15 | left += 1
|
Objective
To iterate through the string with the right pointer, update character counts and max frequency, and shrink the window when replacements exceed k.
Key Insight
By expanding the window and updating counts, the algorithm captures the current substring's character distribution. The key condition checks if the number of characters needing replacement (window size minus max_freq) exceeds k. If so, shrinking the window from the left restores validity. This dynamic adjustment ensures the window always represents a feasible substring under the replacement constraint.
Interview Quick-Check
Core Logic
The window expands by moving the right pointer and updates counts; if the window becomes invalid (needs more than k replacements), the left pointer moves forward to shrink it.
State & Boundaries
The while loop condition ensures the window size minus max_freq never exceeds k, maintaining the replacement limit.
Common Pitfalls & Bugs
Not decrementing the count of the character at the left pointer when shrinking the window leads to incorrect frequency tracking.
Complexity
Each character is processed at most twice, once when expanding and once when shrinking the window, ensuring O(n) time.
Track and Return the Maximum Valid Substring Length
| 17 | max_length = max(max_length, right - left + 1)
|
| 19 | return max_length |
Objective
To update the maximum length of a valid substring found so far and return it after processing the entire string.
Key Insight
By continuously updating max_length with the current window size when valid, the algorithm ensures the longest feasible substring is recorded. Returning this value at the end provides the final answer.
Interview Quick-Check
Core Logic
max_length is updated only when the window is valid, ensuring it always reflects the longest substring achievable with at most k replacements.
State & Boundaries
The final return statement outputs the maximum length found after the full traversal.
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.
counts = {}Initialize a dictionary to count character frequencies in the current window.
This dictionary is essential for tracking how many times each character appears in the sliding window, enabling quick frequency updates and lookups.
counts[char] = 1 + counts.get(char, 0)Increment the frequency count for the current character in the window.
Updating counts ensures the frequency dictionary accurately reflects the current window's character distribution.
counts[s[left]] -= 1Decrement the frequency count of the character at the left pointer as the window shrinks.
Adjusting counts when shrinking the window maintains accurate frequency tracking for the new window boundaries.
max_length = max(max_length, right - left + 1)Update max_length with the size of the current valid window if it is larger.
Tracking the maximum window size ensures the algorithm returns the longest valid substring found during traversal.
max_length = 0Initialize max_length to store the length of the longest valid substring found.
This variable accumulates the maximum window size that satisfies the replacement constraint, which is the final result.
left += 1Move the left pointer forward to shrink the window.
Advancing the left pointer reduces the window size, restoring validity when too many replacements are required.
return max_lengthReturn the length of the longest valid substring found.
This final return provides the solution to the problem after processing the entire string.
left = 0Set the left pointer of the sliding window to the start of the string.
The left pointer marks the beginning of the current substring window and will move forward to shrink the window when necessary.
for right in range(len(s)):Iterate over the string with the right pointer expanding the window.
The right pointer moves forward to explore larger substrings and update character frequencies dynamically.
char = s[right]Get the current character at the right pointer.
Identifying the character to update its frequency count is necessary for tracking the window's composition.
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?
Because the minimum number of replacements needed to make all characters in the window identical equals the window size minus the count of the most frequent character; tracking this max frequency allows efficient validation of the window's validity.
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