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.
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.
1class Solution:
2 def characterReplacement(self, s: str, k: int) -> int:
3 count = [0] * 26
4 left = 0
5 maxFreq = 0
6 maxLength = 0
7 for right in range(len(s)):
8 count[ord(s[right]) - ord('A')] += 1
9 maxFreq = max(maxFreq, count[ord(s[right]) - ord('A')])
10 if right - left + 1 - maxFreq > k:
11 count[ord(s[left]) - ord('A')] -= 1
12 left += 1
13 maxLength = max(maxLength, right - left + 1)
14 return maxLength
15
16# Example usage:
17solution = Solution()
18print(solution.characterReplacement("AABABBA", 1)) # Output: 4We track character counts using a fixed-size list count and adjust windows based on the maximum character frequency. The solution calculates maximum substring length by ensuring the number of different characters (changes) doesn't exceed k.