Longest Repeating Character Replacement

Problem Statement

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.

Approach: Sliding Window

We can use a sliding window approach to find the longest substring with at most k characters different from the most frequent character in that substring.

1. Initialize two pointers, left and right, both at index 0. These represent our current sliding window.
2. Use a Map count to keep track of the frequencies of the characters currently in the window.
3. Keep track of the maximum frequency of a single character in the window (maxf), initialized to 0.
4. Keep track of the maximum length found so far (maxLength), initialized to 0.
5. While right is less than the length of the string:
   • Increment the frequency of the character at s[right] in the count map.
   • Update maxf to be the maximum of its current value and the new frequency of s[right].
   • The number of characters we need to replace in the current window is (right - left + 1) - maxf.
   • If this number is greater than k:
     • The current window is invalid. We must shrink it from the left.
     • Decrement the frequency of s[left] in the count map.
     • Increment left to shrink the window.
   • Update maxLength with the current window size (right - left + 1).
   • Increment right to expand the window.
6. Return the maxLength.

Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
function characterReplacement(s, k) {
    const count = new Map();
    let left = 0;
    let right = 0;
    let maxLength = 0;
    let maxf = 0;
    
    while (right < s.length) {
        count.set(s[right], (count.get(s[right]) || 0) + 1);
        maxf = Math.max(maxf, count.get(s[right]));
        
        while ((right - left + 1) - maxf > k) {
            count.set(s[left], count.get(s[left]) - 1);
            left++;
        }
        
        maxLength = Math.max(maxLength, right - left + 1);
        right++;
    }
    
    return maxLength;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the string. In the worst case, each character is visited at most twice (once by right and once by left). Looking up and updating the map takes $O(1)$ time since there are at most 26 uppercase English letters.
• Space Complexity: $O(1)$. We store at most 26 key-value pairs (one for each uppercase English letter) in the count map, which takes constant extra space.