学习记录：js算法（二十一）：字符串的排列、替换后的最长重复字符

字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false

我的思路
老样子，循环，写的时候还是用了 Map()
网上思路
使用滑动窗口

我的思路

function checkInclusion(s1, s2) {
    const len1 = s1.length;
    const len2 = s2.length;
    if (len1 > len2) return false;
    const count1 = new Map();
    const count2 = new Map();
    for (let char of s1) {
        count1.set(char, (count1.get(char) || 0) + 1);
    }
    for (let i = 0; i < len1; i++) {
        count2.set(s2[i], (count2.get(s2[i]) || 0) + 1);
    }
    if (mapsEqual(count1, count2)) return true;
    for (let i = len1; i < len2; i++) {
        count2.set(s2[i], (count2.get(s2[i]) || 0) + 1);
        const oldChar = s2[i - len1];
        count2.set(oldChar, count2.get(oldChar) - 1);
        if (count2.get(oldChar) === 0) {
            count2.delete(oldChar);
        }
        if (mapsEqual(count1, count2)) return true;
    }
    return false;
}
function mapsEqual(map1, map2) {
    if (map1.size !== map2.size) return false;
    for (let [key, value] of map1) {
        if (map2.get(key) !== value) return false;
    }
    return true;
}

讲解

1. 首先获取 s1 和 s2 的长度。如果 s1 的长度大于 s2，直接返回 false，因为不可能在一个更短的字符串中找到一个更长的字符串的排列。
2. 创建两个 Map，count1 用于存储 s1 中每个字符的频率，count2 用于存储 s2 中当前窗口（长度为 len1）的字符频率。
3. 遍历 s1 中的每个字符，使用 Map 的 set 方法 更新字符频率。如果该字符已经存在于 count1 中，则频率加 1；如果不存在，则初始化为 1。 同样地，遍历 s2 的前 len1 个字符，填充 count2。
4. 在填充完 count2 后，首先检查 count1 和 count2 是否相等。如果相等，说明 s2 的前 len1 个字符就是 s1 的一个排列，返回 true。
5. 使用 for 循环遍历 s2，从 len1 到 len2：
   将当前字符 s2[i] 加入到 count2 中，更新其频率。
   计算滑动窗口的左边界字符 s2[i - len1]，将其频率减 1。如果减到 0，则从 count2 中删除该字符。
6. 每次更新 count2 后，检查 count1 和 count2 是否相等。如果相等，返回 true。
7. 辅助函数 mapsEqual： 用于比较两个 Map 是否相等。
   首先检查两个 Map 的大小是否相等，如果不相等，返回 false。
   然后遍历 map1，检查 map2 中是否存在相同的键和对应的值。如果有不匹配的情况，则返回 false。
   如果所有键值对都匹配，则返回 true。

网上思路

var checkInclusion = function (s1, s2) {
    const s1Length = s1.length;
    const s2Length = s2.length;
    if (s1Length > s2Length) return false;
    const s1Count = Array(26).fill(0);
    const s2Count = Array(26).fill(0);
    // 统计 s1 中每个字符的频率
    for (let i = 0; i < s1Length; i++) {
        s1Count[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;
        s2Count[s2.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    }
    // 比较 s1Count 和 s2Count
    const checkEqual = (a, b) => {
        for (let i = 0; i < 26; i++) {
            if (a[i] !== b[i]) return false;
        }
        return true;
    };
    if (checkEqual(s1Count, s2Count)) return true;
    // 滑动窗口
    for (let i = s1Length; i < s2Length; i++) {
        s2Count[s2.charCodeAt(i) - 'a'.charCodeAt(0)]++;
        s2Count[s2.charCodeAt(i - s1Length) - 'a'.charCodeAt(0)]--;
        if (checkEqual(s1Count, s2Count)) return true;
    }
    return false;
};

讲解

1. 计算 s1 和 s2 的长度。如果 s1 的长度大于 s2，则不可能包含其排列，直接返回 false。
2. 创建两个数组 s1Count 和 s2Count，大小为 26（对应英文字母 a-z），用来统计每个字符的出现频率。
3. 循环，统计 s1 和 s2 的前 s1Length 个字符的频率。
4. 比较频率数组
   定义一个辅助函数 checkEqual，用于比较两个频率数组是否相等。
   如果 s1Count 和 s2Count 相等，说明 s2 的前 s1Length 个字符是 s1 的一个排列，直接返回 true。
5. 滑动窗口遍历 s2
   从 s1Length 开始，遍历 s2 的剩余部分，使用滑动窗口的方式更新 s2Count。每次添加一个新字符 s2[i] 并移除一个旧字符 s2[i - s1Length] 。
   每次更新后，检查 s1Count 和 s2Count 是否相等。

替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

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

示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。

我的思路
循环
网上思路
滑动窗口

我的思路

var characterReplacement = function (s, k) {
    let maxLength = 0;
    for (let start = 0; start < s.length; start++) {
        for (let end = start; end < s.length; end++) {
            const substring = s.slice(start, end + 1);
            const charCount = new Array(26).fill(0);
            for (let char of substring) {
                charCount[char.charCodeAt() - 'A'.charCodeAt()]++;
            }
            const maxCount = Math.max(...charCount);
            const changesNeeded = substring.length - maxCount;
            if (changesNeeded <= k) {
                maxLength = Math.max(maxLength, substring.length);
            }
        }
    }
    return maxLength;
}

讲解

1. 外层循环用于确定子字符串的起始位置。
2. 内层循环用于确定子字符串的结束位置。
3. 使用 slice 方法获取从 start 到 end 的子字符串。
4. 使用一个数组 charCount 来记录当前子字符串中每个字符的频率。
5. 计算当前子字符串中字符的最大频率 **maxCount ** 。
6. 计算将当前子字符串变为相同字符所需的更改次数 **changesNeeded ** 。
7. 如果所需的更改次数小于或等于 k，则更新最长子字符串的长度。

网上思路

var characterReplacement = function (s, k) {
    const count = new Array(26).fill(0); // 用于记录字符频率
    let left = 0; // 左指针
    let maxCount = 0; // 当前窗口内字符的最大频率
    let maxLength = 0; // 最长子字符串的长度
    for (let right = 0; right < s.length; right++) {
        // 更新当前字符的频率
        count[s[right].charCodeAt() - 'A'.charCodeAt()]++;
        // 更新窗口内的最大字符频率
        maxCount = Math.max(maxCount, count[s[right].charCodeAt() - 'A'.charCodeAt()]);
        // 如果当前窗口的大小减去最大频率大于 k，则需要缩小窗口
        while (right - left + 1 - maxCount > k) {
            count[s[left].charCodeAt() - 'A'.charCodeAt()]--;
            left++;
        }
        // 更新最长子字符串的长度
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

讲解
这个看了讲解，很细，先看网上的思路：

1. 定义窗口：使用两个指针 left 和 right 来表示当前窗口的范围。
2. 记录字符频率：使用一个数组或对象来记录当前窗口中每个字符的频率。
3. 计算最大频率：在每次扩展窗口时，计算当前窗口内字符的最大频率。
4. 判断窗口有效性：如果窗口的大小减去最大频率大于 k，则说明需要缩小窗口。
5. 更新最大长度：在每次调整窗口后，更新最长的子字符串长度。

结合代码：

1. 字符频率数组：
   count 数组用于记录每个字符**（A-Z）**的频率。数组大小为 26，因为只有 26 个大写字母。
2. 左右指针：
   left 指针用于表示当前窗口的左边界。
   maxCount 用于记录当前窗口内字符的最大频率。
   maxLength 用于记录找到的最长只包含相同字母的子字符串的长度。
3. 遍历字符串：
   使用 right 指针遍历字符串 s，不断扩展窗口
4. 更新字符频率：
   每次扩展 right 指针时，更新当前字符的频率。通过 charCodeAt() 方法获取字符的 ASCII 码并计算其在 count 数组中的索引。
5. 更新最大频率：
   更新窗口内的最大字符频率 **maxCount ** 。
6. 判断窗口有效性：
   如果当前窗口的大小减去最大频率大于 k，则说明需要缩小窗口。通过移动 left 指针来实现。
   在缩小窗口的同时，更新 count 数组中对应字符的频率。
7. 更新最长子字符串的长度：
   在每次调整窗口后，更新最长的子字符串长度，计算当前窗口的大小 right - left + 1。
8. 返回结果：
   最后返回找到的最长只包含相同字母的子字符串的长度。

总结

之前学习的知识在现在能用上了，比如 Map，双指针 等等，虽然我用的磕磕绊绊，甚至有的还无法结合在一起解题。但是，还是那句话：循环真好用！