1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/longest-repeating-character-replacement/description/

2.解题方法

2.1.解题思路

滑动窗口

2.2.解题步骤

第一步，构建维护变量。left和right分别维护滑动窗口的左右端点；cnts维护滑动窗口中的字符频数

第二步，遍历右指针；并固定右指针，右移左指针，缩小滑动窗口找到最大满足条件的窗口长度

3.解题代码

python代码

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # 思路：滑动窗口
        n = len(s)
        # 第一步，构建维护变量。left和right分别维护滑动窗口的左右端点；cnts维护滑动窗口中的字符频数
        left, right = 0, 0
        cnts = [0] * 26
        result = 0
        # 第二步，遍历右指针；并固定右指针，右移左指针，缩小滑动窗口找到最大满足条件的窗口长度
        while right < n:
            cnts[ord(s[right]) - ord('A')] += 1
            while right - left + 1 - max(cnts) > k:
                cnts[ord(s[left]) - ord('A')] -= 1
                left += 1
            result = max(result, right - left + 1)
            right += 1
        return result

c++代码

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        vector<int> cnts(26, 0);
        int left = 0, right = 0;
        int result = 0;
        while (right < n) {
            cnts[s[right] - 'A'] += 1;
            while (right - left + 1 - *max_element(cnts.begin(), cnts.end()) > k) {
                cnts[s[left] - 'A'] -= 1;
                left++;
            }
            result = max(result, right - left + 1);
            right++;
        }
        return result;
    }
};

4.执行结果