最长重复字符替换 题目描述 给你一个字符串 s 和一个整数 k。你可以选择字符串中的任意一个字符，并将其替换成另一个字符，这样的操作最多可以进行 k 次。在执行上述操作后，找到包含相同字母的最长子串的长度。 示例 输入：s = "ABAB", k = 2 输出：4 解释：将两个 'A' 替换成 'B'，或者将两个 'B' 替换成 'A'，整个字符串就变成了 "AAAA" 或 "BBBB"。 解题过程 这个问题可以使用滑动窗口结合动态规划的思想来解决。核心思路是维护一个窗口，使得窗口内的字符可以通过最多 k 次替换变成全部相同的字符。 关键观察 对于窗口 [ left, right ]，我们需要知道窗口内哪个字符出现次数最多 窗口长度 - 最大出现次数 = 需要替换的字符数量 当需要替换的字符数量 ≤ k 时，窗口是有效的 我们的目标是找到最大的有效窗口 详细步骤 步骤1：定义变量 使用一个数组 count 来记录窗口内每个字符的出现次数 maxCount 记录窗口内出现次数最多的字符的出现次数 left 和 right 表示窗口的左右边界 maxLength 记录找到的最大有效子串长度 步骤2：滑动窗口过程 初始化所有变量为0 右指针 right 从0开始遍历字符串： 将当前字符加入窗口，更新对应字符的计数 更新 maxCount 为当前窗口内字符的最大出现次数 计算当前窗口需要替换的字符数： (right - left + 1) - maxCount 如果需要替换的字符数 > k： 移动左指针，缩小窗口 更新左指针指向字符的计数 更新最大长度 maxLength 步骤3：具体示例分析 以 s = "AABABBA", k = 1 为例： 初始状态：left=0, right=0, maxLength=0 count = [ 0,0,...,0 ], maxCount=0 遍历过程： right=0: 字符'A' count[ 'A' ]=1, maxCount=1 窗口长度=1, 需要替换=0 ≤1 ✓ maxLength=1 right=1: 字符'A' count[ 'A' ]=2, maxCount=2 窗口长度=2, 需要替换=0 ≤1 ✓ maxLength=2 right=2: 字符'B' count[ 'B' ]=1, maxCount=2 窗口长度=3, 需要替换=1 ≤1 ✓ maxLength=3 right=3: 字符'A' count[ 'A' ]=3, maxCount=3 窗口长度=4, 需要替换=1 ≤1 ✓ maxLength=4 right=4: 字符'B' count[ 'B' ]=2, maxCount=3 窗口长度=5, 需要替换=2 >1 ✗ 移动左指针：left=1, count[ 'A' ]=2 窗口长度=4, 需要替换=1 ≤1 ✓ maxLength=4 right=5: 字符'B' count[ 'B' ]=3, maxCount=3 窗口长度=5, 需要替换=2 >1 ✗ 移动左指针：left=2, count[ 'A' ]=1 窗口长度=4, 需要替换=1 ≤1 ✓ maxLength=4 right=6: 字符'A' count[ 'A' ]=2, maxCount=3 窗口长度=5, 需要替换=2 >1 ✗ 移动左指针：left=3, count[ 'B' ]=2 窗口长度=4, 需要替换=1 ≤1 ✓ maxLength=4 最终结果：4 步骤4：算法实现要点 时间复杂度：O(n)，每个字符最多进出窗口一次 空间复杂度：O(1)，只需要固定大小的计数数组 关键优化：不需要每次都重新计算maxCount，因为窗口扩大时maxCount可能增加，窗口缩小时maxCount可能减少但不影响结果正确性 步骤5：边界情况处理 空字符串：返回0 k=0：退化为找最长连续相同字符子串 k ≥ 字符串长度：可以替换所有字符，返回字符串长度 这个解法巧妙地利用了滑动窗口和字符计数的特性，在O(n)时间内解决了问题，是线性动态规划思想的典型应用。