LeetCode刷题实战424：替换后的最长重复字符

我会带着你远行 2022-08-28 00:58 31阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 **替换后的最长重复字符**，我们先来看题面：

https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/

> You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
> 
> Return the length of the longest substring containing the same letter you can get after performing the above operations.

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 10的4次方。

## **示例** ##

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

## **解题** ##

思路 ：

由于题目是问最长子串，这种题目动态规划或者滑动窗口需要着重考虑一下，因为都是当前状态都是和之前相邻的状态有关。

1.先固定左边界，右边界一直右移，直到当前区间内的需要替换的字母数大于k。

2.之后左边界右移，直到该区间需要替换的字母数小于等于k。重复1步骤。

问题是怎么找出某个区间内需要替换的字母数。

答案是用一个maxCnt数组记录各字母在当前区间内的出现次数，出现最多的，我们认为它就是主要字母，其他字母都替换为它。这样总的替换次数是最少的。

class Solution {
    public:
        int characterReplacement(string s, int k) {
            vector<int> counts(26, 0); //记录当前窗口字母出现的个数
            int left=0, res=0, maxCnt=0; // maxCnt记录字符出现次数最多那个字符 的次数
            for(int i=0; i<s.size(); i++){
                counts[s[i]-'A']++;
                maxCnt = max(maxCnt, counts[s[i]-'A']); // 比较之前记录的最大数 和 当前字符的数量
                while(i-left+1-maxCnt > k){ // 若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时
                    counts[s[left]-'A']--; // 将窗口最左边的字符 在计数数组中减1
                    left++; // 滑动窗口
                }
                res = max(res, i-left+1);
            }
            return res;
        }
    };

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个**在看**或者转发吧，你们的支持是我最大的动力 。

**上期推文：**

[LeetCode1-420题汇总，希望对你有点帮助！][LeetCode1-420]

[LeetCode刷题实战421：数组中两个数的最大异或值][LeetCode_421]

[LeetCode刷题实战422：有效的单词方块][LeetCode_422]

[LeetCode刷题实战423：从英文中重建数字][LeetCode_423]

![da154fd9aff91bad2a90e9f41a0c4678.png][]

[LeetCode1-420]: https://blog.csdn.net/itcodexy/article/details/109832160
[LeetCode_421]: https://blog.csdn.net/itcodexy/article/details/121045858
[LeetCode_422]: https://blog.csdn.net/weixin_30853329/article/details/102280906
[LeetCode_423]: https://blog.csdn.net/itcodexy/article/details/120715226
[da154fd9aff91bad2a90e9f41a0c4678.png]: /images/20220828/20fbd45e26dd43a7a18f08a562292b3e.png