LeetCode — longest repeating character after replacement (sliding window)

This is the 14th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

Topic describes

Their thinking

The core solution is: sliding window.

1. Construct an array of 26 elements with the subscripts representing the uppercase letters A-z.

let letterArr = new Array(26).fill(0);
Copy the code

2. Defines the left and right boundaries of the sliding window and the number of occurrences of the most frequent letters in the sliding window.

// Define the left edge of the sliding window
let left = 0;
// Define the right margin of the sliding window
let right = 0;
// Define the number of letters that appear the most in the sliding window
let max = 0;
Copy the code

3. When the right boundary is less than the length of the array, enter the body of the loop, first judge which letter of the element pointed to by the right boundary of the sliding window, then add 1 to the number of corresponding occurrences, and then update the maximum value. If the sliding window does not meet the condition, update the left boundary; otherwise, update the right boundary.

while (right < s.length) {
    // Determine which letter is pointed to by the right margin of the sliding window, and increase its count by 1 accordingly
    let sub = s[right].charCodeAt() - 65;
    letterArr[sub]++;
    // Update by comparing the number of occurrences of the letters pointed to by the right margin with the maximum
    max = Math.max(max, letterArr[sub]);
    // Determine whether to update the left boundary or the right boundary
    if (right - left + 1 > max + k) {
        // Update the left edge
        letterArr[s[left].charCodeAt() - 65]--;
        left++;
        letterArr[s[right].charCodeAt() - 65]--;
    } else{ right++; }}Copy the code

4. Returns the length of the sliding window

return s.length - left;
Copy the code

AC code

var characterReplacement = function (s, k) {
    // Core idea: sliding window
    // Construct an array of all uppercase letters with subscripts representing the elements A to Z and values representing the number of occurrences in the sliding window
    let letterArr = new Array(26).fill(0);
    // Define the left edge of the sliding window
    let left = 0;
    // Define the right margin of the sliding window
    let right = 0;
    // Define the number of letters that appear the most in the sliding window
    let max = 0;

    while (right < s.length) {
        // Determine which letter is pointed to by the right margin of the sliding window, and increase its count by 1 accordingly
        let sub = s[right].charCodeAt() - 65;
        letterArr[sub]++;
        // Update by comparing the number of occurrences of the letters pointed to by the right margin with the maximum
        max = Math.max(max, letterArr[sub]);
        // Determine whether to update the left boundary or the right boundary
        if (right - left + 1 > max + k) {
            // Update the left edge
            letterArr[s[left].charCodeAt() - 65]--;
            left++;
            letterArr[s[right].charCodeAt() - 65]--;
        } else{ right++; }}return s.length - left;
};
Copy the code

The title to reflect

• Learn to use array indices and values to indicate the number of occurrences of certain elements.
• Learn to use sliding Windows to solve substitutions in arrays.