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 <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int characterReplacement(string s, int k) {
7 int left = 0, right = 0, maxFreq = 0, maxLength = 0;
8 vector<int> count(26, 0);
9 while (right < s.size()) {
10 count[s[right] - 'A']++;
11 maxFreq = max(maxFreq, count[s[right] - 'A']);
12 if (right - left + 1 - maxFreq > k) {
13 count[s[left] - 'A']--;
14 left++;
15 }
16 maxLength = max(maxLength, right - left + 1);
17 right++;
18 }
19 return maxLength;
20}
21
22int main() {
23 string s = "AABABBA";
24 int k = 1;
25 cout << characterReplacement(s, k) << endl; // Output: 4
26 return 0;
27}We use a sliding window with two pointers to traverse the string. The vector count stores frequency counts. We adjust the left pointer if the current window size minus the max frequency exceeds k. We keep track of the maximum window length that satisfies the condition.