最长重复字符替换

题目描述
给定一个字符串s和一个整数k，你可以选择字符串中的任意k个字符，将它们替换成任意大写英文字母。请找出替换后可能得到的最长连续相同字符的子串的长度。

例如：
输入：s = "AABABBA", k = 1
输出：4
解释：将中间的一个'B'替换为'A'，得到"AAAABBA"或"AABAAAA"，最长连续'A'的长度为4。

解题过程

这个问题可以使用滑动窗口（双指针）结合动态规划思想来解决。核心思路是维护一个滑动窗口，保证窗口内最多有k个字符可以被替换，从而使得窗口内所有字符相同。

基本概念

• 我们维护一个窗口[l, r]，用哈希表/数组记录窗口内各字符的出现次数
• 关键变量：maxCount记录窗口内同一字符的最大出现次数
• 窗口有效性条件：窗口长度 - maxCount ≤ k

详细步骤

1. 初始化

l = 0  # 左指针
max_count = 0  # 窗口内单个字符的最大出现次数
char_count = [0] * 26  # 记录26个大写字母的出现次数
result = 0

2. 滑动窗口过程
   对于每个右指针r（从0到n-1）：

• 将s[r]对应的计数加1
• 更新max_count为当前窗口内所有字符计数的最大值
• 检查窗口是否有效：如果(窗口长度 - max_count) > k，则需要收缩左边界

3. 窗口有效性判断

while (r - l + 1 - max_count) > k:
    # 窗口无效，需要收缩左边界
    char_count[ord(s[l]) - ord('A')] -= 1
    l += 1
    # 注意：这里不需要更新max_count，因为即使max_count变小，窗口也会继续收缩

4. 更新结果
   每次窗口有效时，用当前窗口长度更新最终结果。

完整算法

def characterReplacement(s, k):
    n = len(s)
    l = 0
    max_count = 0
    char_count = [0] * 26
    result = 0
    
    for r in range(n):
        # 右指针字符计数加1
        idx_r = ord(s[r]) - ord('A')
        char_count[idx_r] += 1
        
        # 更新窗口内最大字符计数
        max_count = max(max_count, char_count[idx_r])
        
        # 检查窗口是否有效
        while (r - l + 1 - max_count) > k:
            # 收缩左边界
            idx_l = ord(s[l]) - ord('A')
            char_count[idx_l] -= 1
            l += 1
        
        # 更新结果
        result = max(result, r - l + 1)
    
    return result

算法分析

• 时间复杂度：O(n)，每个字符最多被左右指针各访问一次
• 空间复杂度：O(1)，只使用了固定大小的数组

关键点说明

1. 为什么不需要实时更新max_count？

   • 当窗口收缩时，max_count可能变小，但这不影响结果正确性
   • 因为我们关心的是历史最大值，即使当前max_count变小，结果也已经记录下了之前找到的最大窗口

2. 算法正确性保证

   • 窗口有效性条件确保最多替换k个字符就能让窗口内字符全部相同
   • 通过滑动窗口遍历所有可能的有效子串

3. 边界情况处理

   • 空字符串：直接返回0
   • k=0：退化为寻找最长连续相同字符子串
   • k≥n：整个字符串都可以被替换为同一字符，返回n

这个算法巧妙地利用了滑动窗口和字符计数的特性，高效地解决了问题。