LeetCode中怎么替换后的最长重复字符串
发表于:2024-09-22 作者:千家信息网编辑
千家信息网最后更新 2024年09月22日,LeetCode中怎么替换后的最长重复字符串,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。题目描述:给你一个仅由大写英文字母组成的字符串
千家信息网最后更新 2024年09月22日LeetCode中怎么替换后的最长重复字符串
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 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中怎么替换后的最长重复字符串的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注行业资讯频道,感谢各位的阅读!
字符
最长
字符串
移动
右边
字母
两个
内容
方法
更多
示例
长度
问题
解释
输入
输出
束手无策
为此
位置
原因
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
软件开发的功能周期包括
dell服务器管理口不亮
北京企业软件开发收费
网络安全能发顶会吗
个人电脑搭建手游游戏服务器
武汉临空港网络安全学院华科
网络安全培训 答案
微信软件开发类图片素材
steam登陆战地五哪个服务器
服务器搭建电话
古籍单机数据库
优周管理服务器
青海省网络安全知识竞答
吉林省ipfs服务器云服务器
多台云服务器如何快捷管理
网络安全工作室赚钱吗
打手机号显示无法连接到服务器
对计算机网络技术的发展
惠普服务器 定时开机
福建联想服务器虚拟化
管家婆服务器版本不对
mysql数据库密码设置错误
怎么开启服务器9573端口
软件开发真实写照
如何把音乐放到数据库
功能强大的电脑软件开发平台
荷泽天气预报软件开发
无线网络技术课程描述
sql大于10万条数据库
搜云数据库压缩包