统计只含单一字符的最长子串的变种——最多允许替换k次字符的最长子串 题目描述 给定一个字符串s和一个整数k，你需要找到最长的子串，使得该子串在最多进行k次字符替换后，能够变成由单一字符组成的子串。换句话说，就是找到一个子串，其中出现次数最多的字符的出现次数，加上k，不小于子串的长度。 解题过程 问题分析 我们需要找到一个子串，通过最多k次替换，可以使其所有字符相同。这等价于：子串的长度减去该子串中出现次数最多的字符的次数，差值不超过k。即： 子串长度 - max_count <= k 。 滑动窗口思路 这是一个典型的滑动窗口问题。我们可以维护一个窗口，用两个指针left和right表示窗口的左右边界。用一个频率数组或哈希表记录窗口内各字符的出现次数。同时，我们维护窗口内出现次数的最大值max_ count。 当 窗口长度 - max_count <= k 时，当前窗口是有效的，我们可以尝试扩大窗口（right右移）。 当 窗口长度 - max_count > k 时，当前窗口无效，我们需要缩小窗口（left右移）。 但这里有一个关键点：当窗口缩小时，max_ count可能需要更新。然而，实际上我们并不需要实时更新max_ count。因为我们的目标是最大化窗口长度，即使当前窗口的max_ count不是精确的，只要它不超过历史最大值，且窗口长度满足条件，我们就可以继续扩展窗口。当窗口变得无效时，我们移动左指针，但max_ count可能保持不变（因为减少的字符可能不是出现最多的字符）。这并不影响最终结果，因为我们在寻找最大窗口，而历史最大值对应的窗口可能已经记录过。 算法步骤 初始化left = 0, max_ count = 0, max_ length = 0。 使用一个频率数组count（大小为26，假设字符串只含小写字母）记录窗口内字符出现次数。 遍历right从0到n-1： 将s[ right ]对应的计数加1。 更新max_ count为max(max_ count, count[ s[ right] - 'a' ])。 检查当前窗口是否有效：如果 (right - left + 1) - max_count > k ，则窗口无效，需要缩小窗口：将s[ left ]的计数减1，left右移一位。 更新最大长度max_ length = max(max_ length, right - left + 1)。 正确性说明 为什么在窗口无效时，只移动left一位，而不更新max_ count？ 因为max_ count记录的是历史最大值，可能比当前窗口的实际最大值大。但这样不会漏解，因为： 我们关心的是最大窗口长度。当窗口扩大时，max_ count可能增加，使得原本无效的窗口变得有效。 如果因为max_ count偏大导致窗口被判断为无效而缩小，那么实际有效的窗口会在后续扩展中被重新考虑。 由于我们每次只移动left一位，且max_ length记录的是历史最大有效窗口，因此最终结果正确。 复杂度分析 时间复杂度：O(n)，其中n为字符串长度。每个字符最多被left和right各访问一次。 空间复杂度：O(1)，因为频率数组大小固定（如26个字母）。 示例 假设s = "AABABBA", k = 1。 right=0: 窗口"A", max_ count=1, 长度1有效，max_ length=1。 right=1: 窗口"AA", max_ count=2, 长度2有效，max_ length=2。 right=2: 窗口"AAB", max_ count=2, 长度3-2=1<=k，有效，max_ length=3。 right=3: 窗口"AABA", max_ count=3, 长度4-3=1<=k，有效，max_ length=4。 right=4: 窗口"AABAB", max_ count=3, 长度5-3=2>k，无效。left右移，窗口变为"ABAB"，max_ count=2（但历史max_ count=3未更新），长度4-2=2>k，仍无效？这里需注意：实际计算时，我们比较的是当前窗口长度和当前max_ count（但当前max_ count可能小于历史值）。在代码实现中，我们使用历史max_ count，但窗口缩小后，实际最大值可能变小，但因为我们不更新max_ count，所以可能仍判断为无效，但这不影响，因为最大窗口4已经记录。继续移动left直到窗口有效。 最终最大长度为4（如将第一个B替换为A，得到"AAAAB"不是全A，但窗口"AABA"本身出现最多的是A（3次），替换1次即可全A）。 通过这个步骤，你可以理解如何使用滑动窗口高效解决该问题。