LeetCode 424. Longest Repeating Character Replacement

思路很重要。

给定一个长度n的字符串s和限制k,将s中的部分字符替换(替换次数<=k)后,能得到连续字符(如AAAA)的长度最大为多少?

使用滑动窗口的思路可以在O(n)时间复杂度的情况下解决这个问题。需要记录当前窗口内各个字符的计数值(可以看做分布情况)以及当前窗口的起始点,窗口内最多字符的计数best。我们知道,最多字符的计数best+修改数量k如果还是不能使得当前窗口内的字符都统一的话,就得把窗口缩小(起始点后挪)。窗口缩小时记得把窗口计数更新一下。

这里有一个tricky的地方,best值本来在滑动窗口的时候是要更新的,因为可能窗口过了这个best会变小。但是由于我们要找的只是个最优的值,所以这个情况并不需要考虑对best进行更新,反正它也成不了最优。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注