Replaced Longest Repeating Character#

You have a string consisting of only uppercase English letters, and you can replace any character at any position with another character, up to a maximum of k times. After performing the above operation, find the length of the longest substring containing repeated letters.

Note: The string length and k will not exceed 104.

Example#

Solution#

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    const n = s.length;
    const chars = new Array(26).fill(0);
    let maxn = 0, left = 0, right = 0;
    for(; right < n; ++right){
        const indexRight = s[right].charCodeAt() - "A".charCodeAt();
        chars[indexRight]++;
        maxn = Math.max(maxn, chars[indexRight]);
        if (right - left + 1 - maxn > k) {
            chars[s[left].charCodeAt() - "A".charCodeAt()]--;
            left++;
        }
    }
    return right - left;
};

Idea#

For operations on continuous data, using a double-pointer to maintain a sliding window can be considered. It is also possible to use a dynamic programming approach. For this question, a double-pointer approach is used to maintain the sliding window. The official explanation of this question's approach is quite good, so let's explain it directly using the official approach. We can enumerate each position in the string as the right endpoint and then find the farthest left endpoint position that meets the condition, where the number of characters other than the most frequent one in that interval (i.e., non-longest repeating characters) does not exceed k. We can think about using two pointers to maintain these intervals. Each time the right pointer moves to the right, if the interval still meets the condition, the left pointer does not move; otherwise, the left pointer moves at most one position to ensure that the interval length does not decrease. This approach is meaningful because we are looking for the longest interval. If a longer one is not found, maintaining the length unchanged will not affect the result. When the right pointer moves to the end, the length of the interval corresponding to the left and right pointers must correspond to the length of the longest interval meeting the condition.

Let's simulate this process with the example ABAB 2. After each loop iteration, notice that right === n.

• left:0 right:1 window:AB len:2
• left:0 right:2 window:ABA len:3
• left:0 right:3 window:ABAB len:4
• left:0 right:4 window:ABAB len:5

First, we define n as the string length and initialize an array to record the quantity of each character occurrence. Then we define maxn to record the most frequent occurrence and left and right as two pointers. We enter a loop. First, we obtain the ASCII - 26 value of the character at the right pointer and increment the corresponding value in the record array. Then we use Math.max to obtain the maximum value of the current character occurrence. Note that since we are incrementing the record array one by one, and when the left pointer moves to the right, we decrement the character's value in the array, we only need to obtain the maximum value among the previous maximum and the current maximum for the character being processed. After that, we compare the window's length with k. If the length is greater than k, we decrement the occurrence of the character at the position pointed by the left pointer in the array, and then move the left pointer to the right. Finally, we return the window length right - left, which is actually due to the extra 1 from the "right" after the loop, so it is (right-1)-left+1 === right-left.

Daily Topic#

Reference#