统计只含单一字符的最长子串的变种——最多允许替换k次字符的最长子串 题目描述 给定一个字符串 s 和一个整数 k ，你需要找到最长的子串，使得该子串中最多包含 k 个与子串中主要字符不同的字符（即允许最多替换 k 次字符，使得子串变为全部由同一字符组成）。例如，对于 s = "AABABBA" 和 k = 1 ，最长子串是 "AABAB" （将第二个 'B' 替换为 'A' ，子串变为 "AAAAA" ，长度为 5）。 解题过程 这个问题可以通过滑动窗口（双指针）结合动态规划思想来解决。核心思路是维护一个窗口，统计窗口内出现次数最多的字符的出现次数，并检查窗口大小是否满足“窗口大小 - 最大出现次数 ≤ k”。若满足，则窗口有效，可以尝试扩大窗口；否则，需要缩小窗口。 步骤详解 初始化 使用两个指针 left 和 right 表示窗口的左右边界，初始均指向字符串起始位置。 使用一个频率数组 freq （长度 26，假设字符串仅含大写字母）或哈希表记录窗口内各字符的出现次数。 变量 maxCount 记录窗口内出现次数最多的字符的出现次数。 变量 maxLength 记录最长有效子串的长度。 滑动窗口过程 遍历字符串，右指针 right 每次向右移动一位，更新当前字符的频次，并更新 maxCount 。 检查当前窗口是否有效：若 (right - left + 1) - maxCount > k ，说明需要替换的字符数超过 k ，窗口无效。此时左指针 right 移动一位，并对应字符的频次减 1（注意： maxCount 不需要更新，因为窗口缩小不会增加最大频次，且我们只关心最大长度）。 更新 maxLength = max(maxLength, right - left + 1) 。 关键点说明 为什么不在无效时更新 maxCount ？因为即使窗口内最大频次减少，我们仍希望保持窗口尽可能大，而 maxLength 的记录依赖于历史最大窗口，且缩小窗口时 maxCount 的减少不会影响已记录的最大长度。 时间复杂度：O(n)，空间复杂度：O(1)（仅使用固定大小的频率数组）。 举例验证 以 s = "AABABBA" , k = 1 为例： 初始： left=0 , right=0 , freq['A']=1 , maxCount=1 , 窗口大小=1（有效）。 right=1 ： freq['A']=2 , maxCount=2 , 窗口大小=2（有效）。 right=2 ： freq['B']=1 , maxCount=2 , 窗口大小=3（3-2=1≤k，有效）。 right=3 ： freq['A']=3 , maxCount=3 , 窗口大小=4（4-3=1≤k，有效）。 right=4 ： freq['B']=2 , maxCount=3 , 窗口大小=5（5-3=2>k，无效）。左指针右移， freq['A']=2 ，窗口大小=4（4-3=1≤k，有效）。 继续移动右指针，最终得到 maxLength=5 （对应子串 "AABAB" ）。 通过以上步骤，即可高效求解该问题。