0424. 替换后的最长重复字符【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 滑动窗口

1. 📝 题目描述

• leetcode

给你一个字符串 s 和一个整数 k。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

---

示例 1：

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

示例 2：

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

---

提示：

• 1 <= s.length <= 10^5
• s 仅由大写英文字母组成
• 0 <= k <= s.length

2. 🎯 s.1 - 滑动窗口

c

int characterReplacement(char* s, int k) {
    int count[26] = {0};
    int left = 0, maxFreq = 0, res = 0, len = strlen(s);
    for (int right = 0; right < len; right++) {
        count[s[right] - 'A']++;
        if (count[s[right] - 'A'] > maxFreq) maxFreq = count[s[right] - 'A'];
        if (right - left + 1 - maxFreq > k) {
            count[s[left] - 'A']--;
            left++;
        }
        if (right - left + 1 > res) res = right - left + 1;
    }
    return res;
}

js

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

py

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0] * 26
        left = max_freq = res = 0
        for right in range(len(s)):
            count[ord(s[right]) - 65] += 1
            max_freq = max(max_freq, count[ord(s[right]) - 65])
            if right - left + 1 - max_freq > k:
                count[ord(s[left]) - 65] -= 1
                left += 1
            res = max(res, right - left + 1)
        return res

• 时间复杂度：$O(n)$
• 空间复杂度：$O(|\mathrm{\Sigma }|)$，字符集大小

算法思路：

• 维护窗口内最高频字符数 maxFreq
• 若窗口长度 - maxFreq > $k$，则缩小窗口
• maxFreq 只增不减，不影响正确性