线性动态规划：统计只含单一字符的最长子串

题目描述

给定一个字符串 s 和一个整数 k，你可以执行最多 k 次操作，每次操作可以将字符串中的任意一个字符替换为另一个字符。请找出在执行最多 k 次操作后，能够得到的只包含单一字符的最长子串的长度。

例如：

• 输入：s = "ABAB", k = 2
• 输出：4
• 解释：将两个 'A' 替换为 'B'，或者将两个 'B' 替换为 'A'，可以得到 "AAAA" 或 "BBBB"

解题过程

这个问题可以使用滑动窗口结合动态规划的思想来解决。让我们一步步分析：

1. 问题分析

我们需要找到一个子串，通过最多 k 次字符替换，使得这个子串中的所有字符都相同。换句话说，在窗口内，除了出现次数最多的字符外，其他字符的数量不能超过 k。

2. 关键观察

对于任意一个窗口 [left, right]：

• 设窗口长度为 window_len = right - left + 1
• 设窗口中出现次数最多的字符的出现次数为 max_count
• 那么需要替换的字符数量 = window_len - max_count

当需要替换的字符数量 ≤ k 时，这个窗口是有效的。

3. 滑动窗口解法

我们可以使用双指针（滑动窗口）来解决这个问题：

def characterReplacement(s: str, k: int) -> int:
    left = 0
    max_count = 0
    max_length = 0
    char_count = {}
    
    for right in range(len(s)):
        # 更新当前字符的计数
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # 更新窗口中出现次数最多的字符的出现次数
        max_count = max(max_count, char_count[s[right]])
        
        # 检查当前窗口是否有效
        # 如果无效，移动左指针
        while (right - left + 1) - max_count > k:
            char_count[s[left]] -= 1
            left += 1
        
        # 更新最大长度
        max_length = max(max_length, right - left + 1)
    
    return max_length

4. 算法步骤详解

让我们用例子 s = "AABABBA", k = 1 来逐步演示：

步骤 1：初始化

• left = 0, max_count = 0, max_length = 0
• char_count = {}

步骤 2：右指针移动到位置 0

• s[0] = 'A'
• char_count = {'A': 1}
• max_count = max(0, 1) = 1
• 窗口长度 = 1，需要替换次数 = 1 - 1 = 0 ≤ 1 ✓
• max_length = max(0, 1) = 1

步骤 3：右指针移动到位置 1

• s[1] = 'A'
• char_count = {'A': 2}
• max_count = max(1, 2) = 2
• 窗口长度 = 2，需要替换次数 = 2 - 2 = 0 ≤ 1 ✓
• max_length = max(1, 2) = 2

步骤 4：右指针移动到位置 2

• s[2] = 'B'
• char_count = {'A': 2, 'B': 1}
• max_count = 2 (仍然是 'A')
• 窗口长度 = 3，需要替换次数 = 3 - 2 = 1 ≤ 1 ✓
• max_length = max(2, 3) = 3

步骤 5：右指针移动到位置 3

• s[3] = 'A'
• char_count = {'A': 3, 'B': 1}
• max_count = max(2, 3) = 3
• 窗口长度 = 4，需要替换次数 = 4 - 3 = 1 ≤ 1 ✓
• max_length = max(3, 4) = 4

步骤 6：右指针移动到位置 4

• s[4] = 'B'
• char_count = {'A': 3, 'B': 2}
• max_count = 3 ('A' 仍然最多)
• 窗口长度 = 5，需要替换次数 = 5 - 3 = 2 > 1 ✗
• 移动左指针：char_count['A'] = 2, left = 1
• 窗口长度 = 4，需要替换次数 = 4 - 3 = 1 ≤ 1 ✓
• max_length 保持 4

步骤 7：右指针移动到位置 5

• s[5] = 'B'
• char_count = {'A': 2, 'B': 3}
• max_count = max(3, 3) = 3
• 窗口长度 = 5，需要替换次数 = 5 - 3 = 2 > 1 ✗
• 移动左指针：char_count['A'] = 1, left = 2
• 窗口长度 = 4，需要替换次数 = 4 - 3 = 1 ≤ 1 ✓
• max_length 保持 4

步骤 8：右指针移动到位置 6

• s[6] = 'A'
• char_count = {'A': 2, 'B': 3}
• max_count = 3 ('B' 最多)
• 窗口长度 = 5，需要替换次数 = 5 - 3 = 2 > 1 ✗
• 移动左指针：char_count['B'] = 2, left = 3
• 窗口长度 = 4，需要替换次数 = 4 - 2 = 2 > 1 ✗
• 继续移动左指针：char_count['A'] = 1, left = 4
• 窗口长度 = 3，需要替换次数 = 3 - 2 = 1 ≤ 1 ✓
• max_length 保持 4

最终结果：4

5. 算法复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度。每个字符最多被访问两次（右指针一次，左指针一次）
• 空间复杂度：O(1)，因为字符集大小是固定的（26个字母）

6. 关键点总结

1. 滑动窗口思想：通过维护一个有效窗口来寻找最优解
2. max_count 的更新：我们只需要知道当前窗口中出现次数最多的字符的出现次数
3. 有效性判断：窗口长度 - max_count ≤ k 时窗口有效
4. 左指针移动：当窗口无效时，移动左指针直到窗口重新有效

这个解法巧妙地利用了滑动窗口的特性，避免了暴力枚举所有可能的子串，从而在 O(n) 时间内解决了问题。