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.
1function characterReplacement(s, k) {
2 const count = new Array(26).fill(0);
3 let left = 0, maxFreq = 0, maxLength = 0;
4 for (let right = 0; right < s.length; right++) {
5 count[s.charCodeAt(right) - 65]++;
6 maxFreq = Math.max(maxFreq, count[s.charCodeAt(right) - 65]);
7 if (right - left + 1 - maxFreq > k) {
8 count[s.charCodeAt(left) - 65]--;
9 left++;
10 }
11 maxLength = Math.max(maxLength, right - left + 1);
12 }
13 return maxLength;
14}
15
16console.log(characterReplacement("AABABBA", 1)); // Output: 4;The JavaScript solution implements a similar strategy with an array-based frequency count for A-Z. The window is adjusted for allowed replacements, measuring the feasible maximum substring length.