424. Longest Repeating Character Replacement - Detailed Explanation
Problem Statement
Description:
Given a string s consisting of uppercase English letters and an integer k, you can perform at most k operations on the string. In one operation, you can choose any character of the string and change it to any other uppercase English letter. Your goal is to find the length of the longest substring containing the same letter that can be obtained after performing at most k operations.
Example 1:
- Input:
- s =
"ABAB" - k =
2
- s =
- Output:
4 - Explanation:
Replace two characters (for example, change both 'A's to 'B's or both 'B's to 'A's) to get"AAAA"or"BBBB". The longest substring with repeating characters is of length 4.
Example 2:
- Input:
- s =
"AABABBA" - k =
1
- s =
- Output:
4 - Explanation:
Replace the one character (for example, change the character at index 5 from 'B' to 'A') so that the longest repeating substring becomes"AAAA"with length 4.
Example 3:
- Input:
- s =
"AAAA" - k =
2
- s =
- Output:
4 - Explanation:
The string already contains all identical characters, so even without any replacements the longest substring is of length 4.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists only of uppercase English letters.
- 0 ≤ k ≤ s.length
Hints to Approach the Problem
-
Hint 1:
Consider using a sliding window technique to explore substrings efficiently. -
Hint 2:
Keep track of the frequency of each character within the current window. The key insight is that the window can be turned into a substring with all the same characters if the total number of characters to replace, which is the window length minus the count of the most frequent character, is less than or equal to k. -
Hint 3:
Expand the window as long as it remains valid. If it becomes invalid, shrink the window from the left until it’s valid again.
Approaches
Approach 1: Brute Force (Not Recommended)
- Idea:
Check every possible substring and count the number of changes needed to convert it into a string of identical characters. - Drawbacks:
This approach requires checking all substrings and is computationally expensive (O(n²) or worse), making it impractical for large strings.
Approach 2: Optimal Sliding Window Technique
-
Idea:
Use a sliding window to maintain a current substring and track the frequency of characters in that window. -
Key Observation:
If the length of the window minus the count of the most frequent character is less than or equal to k, then the window can be transformed into a string of repeating characters by replacing the remaining characters. -
Steps:
-
Initialize two pointers (window start and window end).
-
As you expand the window, update the frequency counts.
-
Compute the number of replacements required:
window length - count of most frequent character -
If the number of replacements exceeds k, move the window start pointer to shrink the window.
-
Keep track of the maximum valid window length.
-
Code Implementations
Python Code
Java Code
Complexity Analysis
-
Time Complexity:
The solution traverses the string once using a sliding window. Each character is processed only once. Therefore, the time complexity is O(n), where n is the length of the string. -
Space Complexity:
A frequency array (or dictionary) is used to store counts for 26 uppercase letters. This requires constant space, so the space complexity is O(1).
Step-by-Step Walkthrough
-
Initialization:
- Set
window_startto 0. - Initialize an empty frequency dictionary (or a fixed array of size 26 in Java).
- Set
max_freq(the count of the most frequent character in the current window) to 0. - Set
max_lengthto 0.
- Set
-
Expand the Window:
- Iterate through the string with the pointer
window_end. - For each character, update its frequency count.
- Update
max_freqif the current character’s count is higher than the currentmax_freq.
- Iterate through the string with the pointer
-
Check Validity of Window:
- Calculate the number of characters that need to be replaced:
window length (window_end - window_start + 1) - max_freq - If this number exceeds k, it means the window is not valid. Shrink the window from the left by incrementing
window_startand update the frequency count for that character.
- Calculate the number of characters that need to be replaced:
-
Update Maximum Length:
- After processing each character, update the
max_lengthwith the current window size if it is larger.
- After processing each character, update the
-
Return the Result:
- After the loop ends,
max_lengthholds the length of the longest valid substring.
- After the loop ends,
Common Mistakes
- Not Updating max_freq Correctly:
Failing to update the count of the most frequent character may result in an incorrect window validation. - Incorrect Window Shrinking:
Not shrinking the window when the number of replacements exceeds k can lead to an invalid window being considered. - Edge Case Oversight:
Missing out on cases when k is greater than or equal to the length of the string.
Edge Cases
- String Already Valid:
If the string consists of the same letter, the longest substring is the entire string. - k Greater Than String Length:
When k is large enough to change every character, the answer is the length of the string.
Alternative Variations and Related Problems
- Longest Substring with At Most K Distinct Characters:
Similar sliding window techniques are applied, but here you manage distinct character counts. - Longest Substring Without Repeating Characters:
Another sliding window problem focusing on unique characters. - Rearranging Characters:
Problems where you need to rearrange characters to meet a specific condition often leverage frequency counts.
Related Problems for Further Practice
- Longest Substring with At Most K Distinct Characters
- Longest Substring Without Repeating Characters
- Sliding Window Maximum
- Minimum Window Substring
GET YOUR FREE
Coding Questions Catalog
