线性动态规划：统计只含单一字符的最长子串的变种——最多允许替换k次字符的最长子串

题目描述
给定一个字符串s和一个整数k，你可以将s中最多k个字符替换成任意字符。请找出替换后可能得到的最长连续单一字符子串的长度。例如，s = "AABABBA", k = 1，可以将中间的一个'B'替换为'A'，得到"AAAABBA"，最长单一字符'A'的子串长度为4。

解题过程
这个问题可以通过滑动窗口结合动态规划思想来解决。核心思路是维护一个窗口，窗口内最多有k个字符与目标字符不同，通过调整窗口大小来找到最长有效子串。

1. 问题分析

   • 我们需要找到一个子串，通过最多k次替换，使子串内所有字符相同。
   • 等价于：子串内非目标字符的数量不超过k（这些字符会被替换为目标字符）。
   • 由于目标字符不确定，需要遍历所有可能字符（但可通过滑动窗口避免显式枚举）。

2. 滑动窗口设计

   • 使用双指针left和right表示窗口的左右边界。
   • 维护一个频率数组freq，记录窗口内各字符的出现次数。
   • 关键变量：maxCount记录窗口内同一字符的最大出现次数。
   • 窗口的有效条件：窗口长度 - maxCount ≤ k（即需要替换的字符数不超过k）。

3. 窗口移动规则

   • 右指针right向右移动，更新freq和maxCount。
   • 如果窗口长度 - maxCount > k，则左指针left右移，并更新freq。
   • 记录窗口长度的最大值作为答案。

4. 为什么正确？

   • maxCount是窗口内“可能成为目标字符”的最大频次，窗口长度 - maxCount即为需要替换的字符数。
   • 当条件不满足时，左移left缩小窗口，确保始终满足替换限制。
   • 由于我们只关心最大窗口长度，无需知道具体目标字符。

5. 算法步骤

   • 初始化left = 0, maxCount = 0, maxLength = 0。
   • 遍历right从0到n-1：
     a. 更新freq[s[right]]，并更新maxCount = max(maxCount, freq[s[right]])。
     b. 若窗口长度(right - left + 1) - maxCount > k，则freq[s[left]]减1，left右移。
     c. 更新maxLength = max(maxLength, right - left + 1)。
   • 返回maxLength。

6. 复杂度分析

   • 时间复杂度：O(n)，每个字符最多被左右指针各访问一次。
   • 空间复杂度：O(字符集大小)，如O(26)用于小写字母。

示例演示
s = "AABABBA", k = 1：

• right=0:窗口"A"，maxCount=1，长度1-1=0≤1，maxLength=1。
• right=1:窗口"AA"，maxCount=2，长度2-2=0≤1，maxLength=2。
• right=2:窗口"AAB"，maxCount=2，长度3-2=1≤1，maxLength=3。
• right=3:窗口"AABA"，maxCount=3，长度4-3=1≤1，maxLength=4。
• right=4:窗口"AABAB"，maxCount=3，长度5-3=2>1，左移left至1，窗口"ABAB"，maxCount=2，长度4-2=2>1，左移left至2，窗口"BAB"，maxCount=2，长度3-2=1≤1，maxLength保持4。
• 继续遍历直至结束，最终maxLength=4。