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.
1#include <stdio.h>
2#include <string.h>
3
4int characterReplacement(char * s, int k){
5 int left = 0, right = 0, maxFreq = 0, maxLen = 0;
6 int freq[26] = {0};
7 while (s[right] != '\0') {
8 freq[s[right] - 'A']++;
9 maxFreq = (freq[s[right] - 'A'] > maxFreq) ? freq[s[right] - 'A'] : maxFreq;
10 if (right - left + 1 - maxFreq > k) {
11 freq[s[left] - 'A']--;
12 left++;
13 }
14 maxLen = (right - left + 1) > maxLen ? (right - left + 1) : maxLen;
15 right++;
16 }
17 return maxLen;
18}
19
20int main() {
21 char s[] = "AABABBA";
22 int k = 1;
23 printf("%d\n", characterReplacement(s, k)); // Output: 4
24 return 0;
25}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.