Watch 10 video solutions for Longest Repeating Character Replacement, a medium level problem involving Hash Table, String, Sliding Window. This walkthrough by NeetCode has 657,697 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.
Constraints:
1 <= s.length <= 105s consists of only uppercase English letters.0 <= k <= s.lengthProblem Overview: Given a string s containing uppercase English letters and an integer k, find the length of the longest substring you can convert into a string of identical characters by replacing at most k characters. The goal is to maximize the window length while ensuring no more than k replacements are required.
Approach 1: Brute Force with Frequency Counting (O(n²) time, O(1) space)
Start every substring at index i and extend it one character at a time to index j. Maintain a frequency array for the 26 uppercase characters and track the most frequent character inside the current substring. The number of replacements needed is (window_length - max_frequency). If this value exceeds k, the substring becomes invalid. Although the character set is fixed so the frequency array uses constant space, evaluating all substrings leads to O(n²) time. This method helps build intuition but is too slow for large inputs.
Approach 2: Sliding Window with Frequency Count (O(n) time, O(1) space)
The optimal solution uses a variable-length window with two pointers. Expand the right pointer while updating a frequency array that tracks counts of characters inside the window. Keep a variable maxFreq representing the highest frequency of any character in the current window. The number of replacements required to make the window uniform is window_size - maxFreq. If this exceeds k, shrink the window by moving the left pointer and updating the counts.
The key insight: the window is valid when (right - left + 1) - maxFreq ≤ k. Because the alphabet size is fixed, frequency updates are constant time. Each character enters and leaves the window at most once, producing linear O(n) time. Space remains O(1) due to the fixed-size frequency array. This technique is a classic pattern combining sliding window mechanics with a small hash table or array for counts while scanning a string.
One subtle optimization keeps maxFreq as the historical maximum rather than recomputing it every time the window shrinks. Even if it becomes slightly outdated, the window size constraint still guarantees correctness because the algorithm only expands when a valid window exists. This avoids scanning the entire frequency array repeatedly.
Recommended for interviews: The sliding window with frequency count is the expected solution. Interviewers want to see you recognize the pattern where a window expands greedily and shrinks when a constraint breaks. Mentioning the brute-force approach briefly shows understanding of the problem space, but implementing the O(n) sliding window demonstrates mastery of window-based string problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Count | O(n²) | O(1) | Useful for understanding the replacement condition and verifying logic on small inputs. |
| Sliding Window with Frequency Count | O(n) | O(1) | Optimal approach for interviews and production. Processes each character once using two pointers. |