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

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从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题汇总,希望对你有点帮助!

LeetCode刷题实战421:数组中两个数的最大异或值

LeetCode刷题实战422:有效的单词方块

LeetCode刷题实战423:从英文中重建数字

(0)

相关推荐

  • 实现一个算法,确定一个字符串 s 的所有字符是否全都不同

    示例 1: 输入: s = "leetcode" 输出: false 示例 2: 输入: s = "abc" 输出: true 限制: 0 <= len( ...

  • ​LeetCode刷题实战157:用 Read4 读取 N 个字符

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

  • ​LeetCode刷题实战172:阶乘后的零

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

  • ​LeetCode刷题实战145:二叉树的后序遍历

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

  • ​LeetCode刷题实战397:整数替换

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

  • ​LeetCode刷题实战260:只出现一次的数字 III

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

  • ​LeetCode刷题实战258:各位相加

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

  • ​LeetCode刷题实战257:二叉树的所有路径

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

  • ​LeetCode刷题实战256:粉刷房子

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

  • ​LeetCode刷题实战262:行程和用户

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