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.
1public class Solution {
2 public int characterReplacement(String s, int k) {
3 int[] count = new int[26];
4 int left = 0, maxFreq = 0, maxLength = 0;
5 for (int right = 0; right < s.length(); right++) {
6 count[s.charAt(right) - 'A']++;
7 maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);
8 if (right - left + 1 - maxFreq > k) {
9 count[s.charAt(left) - 'A']--;
10 left++;
11 }
12 maxLength = Math.max(maxLength, right - left + 1);
13 }
14 return maxLength;
15 }
16
17 public static void main(String[] args) {
18 Solution solution = new Solution();
19 System.out.println(solution.characterReplacement("AABABBA", 1)); // Output: 4
20 }
21}We use an integer array count to record character frequencies in the current window. The window expands with the right pointer, and we adjust the left pointer to maintain at most k replacements. We update maxLength during this process.