线性动态规划：最长重复字符替换的最长子串（允许最多K次替换）

题目描述

给你一个字符串 s 和一个整数 k。你可以执行以下操作最多 k 次：将字符串中的任意一个字符替换成另一个字符（通常题目限定为替换为同一个字符，以构造最长重复字符子串）。目标是找到执行最多 k 次替换后，字符串中最长的由相同字符组成的子串的长度。

示例 1:
输入: s = "ABAB", k = 2
输出: 4
解释: 可以将两个 'A' 替换为 'B'，或者将两个 'B' 替换为 'A'，从而得到 "BBBB" 或 "AAAA"，整个字符串都是相同字符，长度为4。

示例 2:
输入: s = "AABABBA", k = 1
输出: 4
解释: 将索引为3的 'A' 替换为 'B'，得到 "AABBBBA"，其中最长的重复字符子串是 "BBBB"，长度为4。

注意: 字符串仅包含大写英文字母，0 <= k <= s.length。

解题思路详解

这个问题是经典的“滑动窗口”与“动态规划”结合的问题，但核心可以通过线性动态规划思想来理解和推导。关键在于如何高效地维护一个窗口，使其在最多 k 次替换的条件下，窗口内的字符尽可能相同。

核心思路

对于一个以索引 j 结尾的窗口，我们想找到最长的子串，使得这个子串在最多 k 次替换后，所有字符都相同。等价地，我们维护一个窗口 [i, j]，使得窗口大小减去窗口内出现次数最多的字符的个数（这个差值就是需要替换的次数）不超过 k。

公式:
对于窗口 [i, j]，设窗口内出现次数最多的字符的频次为 maxFreq。则窗口内需要替换的字符数量为 window_length - maxFreq。如果这个值 <= k，说明这个窗口是有效的，我们可以尝试扩大窗口；否则，我们需要缩小窗口左边界 i 来减少替换次数。

解题步骤

我们将采用滑动窗口（同向双指针）的方法，并结合一个频次数组来记录窗口内字符的出现次数。

步骤 1: 初始化变量

• 使用一个长度26的数组 freq 记录窗口内每个大写字母的出现次数。
• 初始化指针 left = 0 表示窗口左边界，maxFreq = 0 记录窗口内出现最多次的字符的频次，maxLen = 0 记录最终答案。

步骤 2: 遍历字符串（右指针移动）

• 用 right 从0到 n-1 遍历字符串，表示窗口右边界。
• 将 s[right] 对应的频次加1，并更新 maxFreq 为 max(maxFreq, freq[s[right] - 'A'])。maxFreq 记录了当前窗口内出现次数最多的字符的频次。

步骤 3: 检查窗口是否有效

• 计算当前窗口大小 windowSize = right - left + 1。
• 需要替换的次数 = windowSize - maxFreq。
• 如果这个值 > k，说明当前窗口需要替换的次数太多，不满足条件。我们需要缩小窗口左边界：
  • 将 s[left] 对应的频次减1。
  • 左指针 left 右移一位。
  • 注意：此时我们不需要更新 maxFreq，因为即使 maxFreq 可能变小，但 windowSize 也变小了，而且我们只需要记录历史上出现的最大 maxFreq 来帮助找到最长窗口即可（即使后面变小，也不会影响我们计算最大长度）。

步骤 4: 更新最大长度

• 每次窗口有效时，用当前窗口大小更新 maxLen。

步骤 5: 最终结果

• 遍历结束后，maxLen 就是答案。

详细示例解析

以 s = "AABABBA", k = 1 为例：

1. 初始化: left=0, maxFreq=0, maxLen=0, freq=[0,...]
2. right=0: 字符'A'，freq[0]=1, maxFreq=1, 窗口大小1，替换次数=1-1=0<=1，窗口有效，maxLen=1
3. right=1: 字符'A'，freq[0]=2, maxFreq=2, 窗口大小2，替换次数=2-2=0<=1，窗口有效，maxLen=2
4. right=2: 字符'B'，freq[1]=1, maxFreq=2, 窗口大小3，替换次数=3-2=1<=1，窗口有效，maxLen=3
5. right=3: 字符'A'，freq[0]=3, maxFreq=3, 窗口大小4，替换次数=4-3=1<=1，窗口有效，maxLen=4
6. right=4: 字符'B'，freq[1]=2, maxFreq=3, 窗口大小5，替换次数=5-3=2>1，无效。于是移动左指针: 移除s[0]即'A'，freq[0]=2, left=1。此时窗口大小变为4（右指针未动），窗口字符为"ABAB"，maxFreq仍是3（历史最大，但实际当前窗口最多是2个'A'和2个'B'，频次均为2），替换次数=4-3=1<=1，有效。但窗口大小4不大于当前maxLen=4，不更新。
7. right=5: 字符'B'，freq[1]=3, maxFreq=3, 窗口大小5（left=1, right=5），窗口为"ABABB"，替换次数=5-3=2>1，无效。移动左指针: 移除s[1]即'A'，freq[0]=1, left=2。现在窗口大小4，字符"BABB"，maxFreq=3（当前窗口内'B'出现了3次），替换次数=4-3=1<=1，有效，maxLen保持4。
8. right=6: 字符'A'，freq[0]=2, maxFreq=3, 窗口大小5，替换次数=5-3=2>1，无效。移动左指针: 移除s[2]即'B'，freq[1]=2, left=3。窗口大小4，字符"ABBA"，maxFreq=2（当前窗口内最多是2个'A'或2个'B'），替换次数=4-2=2>1，无效。再移动左指针: 移除s[3]即'A'，freq[0]=1, left=4。窗口大小3，字符"BBA"，maxFreq=2，替换次数=3-2=1<=1，有效，maxLen保持4。

最终结果: 4

算法复杂度

• 时间复杂度: O(n)，其中n是字符串长度。左右指针各遍历一次字符串。
• 空间复杂度: O(1)，因为字母表大小固定为26。

关键点总结

• 核心是维护窗口内出现最多次字符的频次 maxFreq。
• 窗口有效条件是 windowSize - maxFreq <= k。
• 当窗口无效时，左指针右移，此时无需更新 maxFreq 为当前窗口实际最大值，因为我们要找的是最长的有效窗口，历史上最大的 maxFreq 能帮助我们在窗口大小更大时仍满足条件。即使当前窗口的 maxFreq 变小，也只会使替换次数增大，窗口会继续缩小，不会错过最优解。

代码实现（Python示例）

def characterReplacement(s: str, k: int) -> int:
    n = len(s)
    if n <= k:
        return n
    
    freq = [0] * 26
    left = 0
    maxFreq = 0
    maxLen = 0
    
    for right in range(n):
        # 右指针字符计数
        idx = ord(s[right]) - ord('A')
        freq[idx] += 1
        # 更新窗口内最大频次
        maxFreq = max(maxFreq, freq[idx])
        
        # 当前窗口大小
        windowSize = right - left + 1
        # 如果替换次数超出k，左指针右移
        if windowSize - maxFreq > k:
            # 左指针字符出窗口
            left_idx = ord(s[left]) - ord('A')
            freq[left_idx] -= 1
            left += 1
            # 窗口大小减小，但maxFreq不更新，因为我们需要历史上最大频次
            windowSize -= 1
        
        # 更新最大长度
        maxLen = max(maxLen, windowSize)
    
    return maxLen

总结：这个问题本质上是利用滑动窗口维护一个满足条件的最长子串，通过频次统计和动态更新 maxFreq 来高效判断窗口的合法性，是线性动态规划在字符串处理中的一个典型应用。