每日算法系列【LeetCode 424】替换后的最长重复字符

简介: 每日算法系列【LeetCode 424】替换后的最长重复字符

题目描述

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

示例1

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

示例2

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

提示字符串长度和 k 不会超过 10^4。

题解

这题和之前做过的一题非常类似:每日算法系列【LeetCode 1004】最大连续1的个数 III只不过这题字符数量变成了 26 个。

方法和那题类似,都是用滑动窗口。用数组 count 记录每个字母出现的次数,并且用变量 cmax 记录窗口中出现次数最多的字母数量。

当前窗口是 [l, r] ,如果保留窗口中出现次数最多的字母,将其他字母全部替换为这个字母,那么替换次数就是  。如果它大于 k ,那就说明不能继续向右扩展,而是需要左端点右移,缩小窗口了。缩小的过程中时刻更新 cmax 的值就行了,直到  再次小于等于 k ,然后继续右移 r 。

代码

c++

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        vector<int> count(26, 0);
        int l = 0, r = 0, cmax = 0, res = 0;
        while (r < n) {
            cmax = max(cmax, ++count[s[r]-'A']);
            while (r - l + 1 - cmax > k)
                count[s[l++]-'A']--;
            res = max(res, r - l + 1);
            r++;
        }
        return res;
    }
};

python

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        count = [0] * 26
        l, r, cmax, res = 0, 0, 0, 0
        while r < n:
            count[ord(s[r])-ord('A')] += 1
            cmax = max(cmax, count[ord(s[r])-ord('A')])
            while r - l + 1 - cmax > k:
                count[ord(s[l])-ord('A')] -= 1
                l += 1
            res = max(res, r - l + 1)
            r += 1
        return res

后记

注意这里代码实现上面有个很大的问题,就是右移左端点缩小窗口的时候, cmax 并没有跟着减小,这样为什么还是对的呢?这种情况下, cmax保存的其实是历史出现次数最多的字母的次数。而你不改变 cmax ,就会导致中间过程中出现很多不符合题意的窗口,也就是实际要修改的数量大于 k 的窗口,但是因为你 cmax 偏大,算下来修改数量偏小,它又是符合题意的。不过不影响,这些错误的窗口的长度一定是小于你之前算到的正确窗口的长度的(如果大于了,那么 cmax 一定会被更新)。

下面解释来自于algsCG:

因为我们只对最长有效的子字符串感兴趣,所以我们的滑动窗口不需要收缩,即使窗口可能覆盖无效的子字符串。我们可以通过在右边添加一个字符来扩展窗口,或者将整个窗口向右边移动一个字符。而且我们只在新字符的计数超过历史最大计数(来自覆盖有效子字符串的前一个窗口)时才增长窗口。也就是说,我们不需要精确的当前窗口的最大计数;我们只关心最大计数是否超过历史最大计数;这只会因为新字符而发生。

相关文章
|
2月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
53 0
|
2月前
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
99 0
Leetcode第三题(无重复字符的最长子串)
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
43 0
|
4月前
|
算法
【算法】位运算算法——判断字符是否唯一
【算法】位运算算法——判断字符是否唯一
|
4月前
|
算法
【算法】滑动窗口——无重复字符的最长子串
【算法】滑动窗口——无重复字符的最长子串
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
29 2
|
4月前
|
算法
LeetCode第3题无重复字符的最长子串
该文章介绍了 LeetCode 第 3 题无重复字符的最长子串的解法,通过使用 HashSet 记录不重复的子元素,以每个字符开头遍历字符串,遇到重复字符则重新计算,最终找到最长子串,同时提到可以考虑使用 HashMap 降低复杂度。
LeetCode第3题无重复字符的最长子串
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
57 6
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
54 1