LeetCode第424题：替换后的最长重复字符

题目描述

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子串的长度。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

提示：

1 <= s.length <= 10^5
s 仅由大写英文字母组成
0 <= k <= s.length

解题思路

这道题可以使用滑动窗口的方法来解决。主要思路如下：

使用滑动窗口维护一个区间，在这个区间内通过k次替换操作，可以将所有字符变成同一个字符。
使用一个数组或哈希表记录窗口内每个字符出现的次数。
对于当前窗口，我们需要找到出现次数最多的字符，记为maxCount。那么需要替换的字符个数就是窗口大小减去maxCount。
如果需要替换的字符个数小于等于k，说明当前窗口是有效的，可以尝试扩大窗口。
如果需要替换的字符个数大于k，说明当前窗口无效，需要缩小窗口。

代码实现

Java代码实现

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int maxCount = 0;
        int left = 0;
        int result = 0;
        
        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'A']++;
            // 更新当前窗口内出现次数最多的字符的出现次数
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            
            // 当前窗口长度减去出现最多字符的次数，就是需要替换的字符个数
            // 如果大于k，说明当前窗口不满足条件，需要缩小窗口
            if (right - left + 1 - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            
            // 更新结果
            result = Math.max(result, right - left + 1);
        }
        
        return result;
    }
}

Python代码实现

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        max_count = 0
        left = 0
        result = 0
        
        for right in range(len(s)):
            # 更新字符计数
            count[s[right]] = count.get(s[right], 0) + 1
            # 更新窗口内出现最多的字符次数
            max_count = max(max_count, count[s[right]])
            
            # 如果当前窗口内需要替换的字符数超过k，缩小窗口
            if right - left + 1 - max_count > k:
                count[s[left]] -= 1
                left += 1
            
            # 更新结果
            result = max(result, right - left + 1)
        
        return result

C++代码实现

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> count(26);
        int maxCount = 0;
        int left = 0;
        int result = 0;
        
        for (int right = 0; right < s.length(); right++) {
            count[s[right] - 'A']++;
            maxCount = max(maxCount, count[s[right] - 'A']);
            
            if (right - left + 1 - maxCount > k) {
                count[s[left] - 'A']--;
                left++;
            }
            
            result = max(result, right - left + 1);
        }
        
        return result;
    }
};

复杂度分析

时间复杂度：O(n)，其中n是字符串的长度。我们只需要遍历一次字符串。
空间复杂度：O(1)，因为我们使用的额外空间是固定的26个字母的计数数组。

题目总结

这是一道典型的滑动窗口题目，关键是要理解如何维护窗口的有效性。
在处理字符串问题时，使用数组来统计字符出现次数是一个常用的技巧。
维护窗口内出现最多字符的次数(maxCount)是解决此问题的关键，它帮助我们判断当前窗口是否有效。
这道题的解法可以推广到类似的问题中，比如寻找可以通过有限次数修改得到的最长特定模式。