424. 替换后的最长重复字符

题目

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

例

输入：s = "AABABBA", k = 1

输出：4

解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。

题解

滑动窗口

424. 替换后的最长重复字符

题目

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

输入:
s = "ABAB", k = 2

输出:
4

解释:
用两个'A'替换为两个'B',反之亦然。

题解

滑动窗口

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
  // 保存窗口内每个字母的个数
  let m = new Map();
  // 滑动窗口的开始位置
  let pos = 0;
  // 窗口内相同字母最多的个数
  let max = 0;
  // 结果
  let res = 0;
  for (let i = 0; i < s.length; ++i) {
    const t = s[i];
    if (!m.has(t)) m.set(t, 1);
    else m.set(t, m.get(t) + 1);
    if (max < m.get(t)) {
      max = m.get(t);
    }
    // 如果 窗口长度 > 相同字母最大值 + k
    // 说明不满足条件,继续移动窗口
    while (i - pos + 1 > max + k) {
      m.set(s[pos], m.get(s[pos]) - 1);
      pos++;
    }
    if (i - pos + 1 > res) {
      res = i - pos + 1;
    }
  }
  return res;
};

时间复杂度：O(n) 空间复杂度：O(x) x 是字符集的大小

双指针

其实和滑动窗口一样

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
  // 统计双指针范围内字符出现次数
  let m = new Array(26).fill(0);

  // 双指针 历史出现最多次数
  let l = (r = max = 0);

  while (r < s.length) {
    m[s[r].charCodeAt() - "A".charCodeAt()]++;
    max = Math.max(max, m[s[r].charCodeAt() - "A".charCodeAt()]);

    // 如果历史最大不满足，就移动左指针，保持窗口大小不变
    if (r - l + 1 > max + k) {
      m[s[l].charCodeAt() - "A".charCodeAt()]--;
      l++;
    }
    r++;
  }
  return r - l;
};