这篇文章主要介绍了leetcode如何求替换后的最长重复字符,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
注意:
字符串长度 和 k 不会超过 104。
示例 1:
输入:s = "ABAB", k = 2输出:4解释:用两个'A'替换为两个'B',反之亦然。
示例 2:
输入:s = "AABABBA", k = 1输出:4解释:将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。子串 "BBBB" 有最长重复字母, 答案为 4。
解题思路
1,滑动窗口类题目一般都需要左右两个指针,重点放在理解和优化窗口移动的逻辑
2,注意本题是提换K个字符而不是替换K种
3,显然最大长度=窗口内出现次数最多的字符的次数+K
4,每次移动右指针,更新最大出现次数
5,如果右指针到左指针长度>K+最大出现次数则,移动左指针
func characterReplacement(s string, k int) int { win:=make(map[byte]int) start:=0 max:=0 maxSame:=0 for end:=0;end<len(s);end++{ win[s[end]]++ if win[s[end]]>maxSame{ maxSame=win[s[end]] } for end-start+1-maxSame>k{ win[s[start]]-- start++ } fmt.Println("*",start,end,maxSame) if end-start+1>max{ max=end-start+1 } } return max}
感谢你能够认真阅读完这篇文章,希望小编分享的“leetcode如何求替换后的最长重复字符”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/4586289/blog/4634808