带你读《图解算法小抄》二十、滑动窗口（4）

带你读《图解算法小抄》二十、滑动窗口（3）https://developer.aliyun.com/article/1347998?groupCode=tech_library

3）JavaScript解题框架：

下面是一个使用JavaScript实现滑动窗口算法解决最长无重复字符子串问题的框架代码：

function lengthOfLongestSubstring(s) {
    let maxLength = 0;
    let left = 0;
    let right = 0;
    let set = new Set();    while (right < s.length) {
        if (!set.has(s[right])) {
            set.add(s[right]);
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        } else {
            set.delete(s[left]);
            left++;
        }
}
    return maxLength;
}

在这个框架中，我们使用了left和right两个指针来构建窗口，set集合用于存储窗口内的字符。我们不断地向右移动right指针，如果遇到重复字符，则移动left指针来缩小窗口。在每次移动right指针时，都会更新最长子串的长度maxLength。最后，我们返回最长子串的长度作为结果。

5.最长重复字符替换

给定一个仅包含大写英文字母的字符串s和一个整数k，你可以对任何字符串中的字符进行最多k次替换。请你找出并返回替换后最长的重复字符子串的长度。

示例:

输入：s = "ABAB", k = 2 输出：4 解释：使用两个'A'替换为两个'B',反之亦然。

输入：s = "AABABBA", k = 1 输出：4 解释：将中间的一个'A'替换为'B',字符串变为"AABBBBA"。 子串 "BBBB" 有最长重复字母, 长度为4。

1）题目分析与解题步骤：

为了解决这个问题，我们可以使用滑动窗口的方法。我们需要找出一个最长的窗口，这个窗口内部最多包含k个不同的字符。我们将这个窗口内的所有其他字符全部替换为出现次数最多的那个字符，就可以得到一个全是同一字符的字符串。

解题步骤如下：

• 初始化两个指针left和right，都指向字符串的开始。
  
• 不断地向右移动right指针，扩大窗口。每次移动时，记录当前窗口中出现次数最多的字符的数量。同时，如果right - left + 1（当前窗口的大小）减去出现次数最多的字符的数量大于k，说明不能通过替换得到全是同一字符的字符串，此时需要移动left指针，缩小窗口。
  
• 每次移动right指针，都尝试用当前窗口的大小更新最长重复字符子串的长度。
  

下面是对应的JavaScript代码：

function characterReplacement(s, k) {
    let count = new Array(26).fill(0);
    let maxCount = 0, maxLength = 0;
    let left = 0, right = 0;    while (right < s.length) {
        count[s.charCodeAt(right) - 'A'.charCodeAt(0)]++;
        maxCount = Math.max(maxCount, count[s.charCodeAt(right) - 'A'.charCodeAt(0)]);        if (right - left + 1 - maxCount > k) {
            count[s.charCodeAt(left) - 'A'.charCodeAt(0)]--;
            left++;
        } else {
            maxLength = Math.max(maxLength, right - left + 1);
        }        right++;
}
    return maxLength;
}

在这段代码中，我们使用了一个数组count来记录每个字符的出现次数，maxCount来记录窗口中出现次数最多的字符的数量，maxLength来记录最长重复字符子串的长度。在每次移动right指针时，我们都会更新count和maxCount，并且如果当前窗口不能通过最多k次替换得到全是同一字符的字符串，我们就会移动left指针，缩小窗口。最后，返回的maxLength就是最长重复字符子串的长度。

带你读《图解算法小抄》二十、滑动窗口（5）https://developer.aliyun.com/article/1347995?groupCode=tech_library