给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换k
次。在执行上述操作后,找到包含重复字母的最长子串的长度。
注意:字符串长度 和k
不会超过104
。
基本对于连续的数据的操作都可以考虑使用双指针维护一个滑动窗口去做,当然也有可能采用动态规划的做法,本题使用双指针维护滑动窗口,这个题目官方的思路比较好,就直接以官方的思路做个解释,我们可以枚举字符串中的每一个位置作为右端点,然后找到其最远的左端点的位置,满足该区间内除了出现次数最多的那一类字符之外,剩余的字符(即非最长重复字符)数量不超过k
个,这样我们可以想到使用双指针维护这些区间,每次右指针右移,如果区间仍然满足条件,那么左指针不移动,否则左指针至多右移一格,保证区间长度不减小,这样做的意义是我们求的是最长,如果找不到更长的维持长度不变返回结果不受影响,当我们右指针移动到尽头,左右指针对应的区间的长度必然对应一个长度最大的符合条件的区间。
我们以示例的ABAB 2
为例来模拟一遍这个过程,过程为每次循环结束的位置,注意第四次循环结束后right===n
。
left:0 right:1 window:AB len:2
left:0 right:2 window:ABA len:3
left:0 right:3 window:ABAB len:4
left:0 right:4 window:ABAB len:5
首先我们定义n
为字符串长度,定义数组并初始化值为0
用以记录各个字符的数量,之后定义maxn
用以记录出现次数最多的值,以及left
与right
两个指针,之后定义循环,首先取得right
指针的ASCII-26
值,将记录数组中这个字符的数量++
,之后使用Math.max
取得当前字符数量出现的最大值,注意此时由于我们是逐个增加记录数组中的值,并且左指针右移时将字符的值--
,所以我们只需要取得之前的最大值与当前处理的字符的数组最大值即可,之后比较窗口的长度与k
的大小,如果长度比k
大则将左指针指向的字符在数组中的统计值--
,之后左指针右移,最后返回窗口长度right - left
即可,实际上是因为循环的最后right
多出1
所以是(right-1)-left+1 === right-left
。