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.
This approach is based on using a sliding window to track the current substring and its character frequencies. Within the window, we maintain the frequency of each character and focus on the most frequent character. By using this information, we determine how many changes are needed to make all characters in the window the same. We adjust the window size based on whether the number of changes required exceeds k.
We initialize two pointers, left and right, to maintain the window. The frequency of each character in the current window is stored in an array freq. As we expand the window by moving right, we update the frequency count, checking if the current window size minus the maximum frequency is greater than k. If so, we move left to reduce the window size. Finally, we calculate the maximum length of the substring observed.
The time complexity is O(n), where n is the length of string s, as we pass over the string with two pointers. Space complexity is O(1) since the frequency array size does not depend on the input size but on the fixed size of the English alphabet.
| 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. |
Longest Repeating Character Replacement - Leetcode 424 - Python • NeetCode • 774,737 views views
Watch 9 more video solutions →Practice Longest Repeating Character Replacement with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor