Medium

题目描述

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

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

示例 1：

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

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：将中间的一个'A'替换为'B'，字符串变为 "AABBBBA"。
子字符串 "BBBB" 的最长重复字母长度为 4。
可能存在其他的方法来得到这个结果。

提示：

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

解题思路

解题思路

这是一道经典的滑动窗口题目。核心思想是维护一个窗口，使得窗口内除了出现频次最多的字符外，其他字符的总数不超过 k 个，这样我们就能通过最多 k 次替换操作使整个窗口变成相同字符。

算法步骤：

  1. 滑动窗口设计：使用双指针 left 和 right 维护窗口边界
  2. 频次统计：用哈希表记录窗口内每个字符的出现次数
  3. 窗口有效性判断：窗口长度 - 最高频次字符数量 ≤ k
  4. 窗口调整：当窗口无效时，移动左指针直到窗口重新有效

关键观察：

  • 我们不需要考虑具体替换哪个字符，只需要保证替换次数不超过 k
  • 窗口内的最优策略是将所有非最高频字符都替换成最高频字符
  • 因此判断条件是：窗口大小 - max_count ≤ k

算法时间复杂度为 O(n)，空间复杂度为 O(1)（最多26个英文字母）。

代码实现

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> count(26, 0);
        int left = 0, maxCount = 0, maxLength = 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++;
            }
            
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        left = 0
        max_count = 0
        max_length = 0
        
        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
            max_count = max(max_count, count[s[right]])
            
            if right - left + 1 - max_count > k:
                count[s[left]] -= 1
                left += 1
            
            max_length = max(max_length, right - left + 1)
        
        return max_length

public class Solution {
    public int CharacterReplacement(string s, int k) {
        int[] count = new int[26];
        int left = 0, maxCount = 0, maxLength = 0;
        
        for (int right = 0; right < s.Length; right++) {
            count[s[right] - 'A']++;
            maxCount = Math.Max(maxCount, count[s[right] - 'A']);
            
            if (right - left + 1 - maxCount > k) {
                count[s[left] - 'A']--;
                left++;
            }
            
            maxLength = Math.Max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    const count = {};
    let left = 0, maxCount = 0, maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        count[s[right]] = (count[s[right]] || 0) + 1;
        maxCount = Math.max(maxCount, count[s[right]]);
        
        if (right - left + 1 - maxCount > k) {
            count[s[left]]--;
            left++;
        }
        
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)其中 n 是字符串长度，每个字符最多被访问两次
空间复杂度O(1)使用固定大小的数组或哈希表存储字符频次，最多26个字母

相关题目