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.lengthThis 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.
C++
Java
Python
C#
JavaScript
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.
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 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