Longest Repeating Character Replacement

Problem

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Constraints:

1 <= s.length <= 10⁵
s consists of only uppercase English letters.
0 <= k <= s.length

Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    let l = 0; // left of window
    let r = 0; // right of window
    let maxFreq = 0; // max frequency of any letter in s[0:r + 1]
    const map = {}; // occurrence of letter in s[l:r + 1]

    for (; r < s.length; r++) {
        const c = s[r];
        if (!(c in map)) {
            map[c] = 0;
        }
        map[c]++;
        maxFreq = Math.max(maxFreq, map[c]);

        // if the window cannot be modified to contain the same letter
        if (r - l + 1 > maxFreq + k) {
            map[s[l]]--;
            l++;
        }
    }
    return r - l;
};

We will implement a sliding window solution. We keep on incrementing the right boundary r of the window, while updating map, maxFreq, as well as checking whether this new window is valid (if invalid we will also increment l so that the size of the window stays the same instead of increasing). More specifically:

If the window did increase in size, then we know it must be valid due to our check (ie. l - r + 1 > maxFreq + k is false)
Otherwise, if the window simply shifts (ie. r++ and l++), there is no guarantee that the new window is valid.

That said, we do know that there must have been a previous window of this size that was valid. Thus, because the size of the window is non-decreasing (only increasing when a longer substring that is valid is found), the length of the longest valid substring is the final window size (ie. r - l).

Problem​

Solution​

Problem

Solution