LeetCode中怎么替换后的最长重复字符串

发布时间：2021-08-02 15:51:13 阅读：247 作者：Leah 栏目：大数据

开发者测试专用服务器限时活动，0元免费领，库存有限，领完即止！点击查看>>

LeetCode中怎么替换后的最长重复字符串，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

题目描述：

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

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

示例 1：

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

示例 2：

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

思路分析：

一看到最长字符串就想到滑动窗口。

算法流程：

右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

class Solution:    def characterReplacement(self, s: str, k: int) -> int:        from collections import defaultdict        d = defaultdict(int)        l = 0        maxn = 0        for r in range(len(s)):            d[s[r]] += 1            maxn = max(maxn, d[s[r]])            if r - l + 1 > maxn + k:  # bc it is for loop, r += 1 is later than if clause                d[s[l]] -= 1                l += 1        return len(s) - l

class Solution {    public int characterReplacement(String s, int k) {        int len=s.length();        if(len<2){            return len;        }        char[] chararray=s.toCharArray();        int left=0,right=0;        int maxCount=0,res=0;        int[] freq = new int[26];        while(right<len){            freq[chararray[right]-'A']++;            maxCount=Math.max(maxCount,freq[chararray[right]-'A']);            right++;            if(right-left>maxCount+k){                freq[chararray[left]-'A']--;                left++;            }            res=Math.max(res,right-left);                    }        return res;    }}

看完上述内容，你们掌握LeetCode中怎么替换后的最长重复字符串的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

向AI问一下细节

LeetCode中怎么替换后的最长重复字符串

题目描述：

示例 1：

示例 2：

思路分析：

算法流程：

猜你喜欢

最新资讯

相关推荐

开发者交流群：

相关标签