替换后的最长重复字符

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

  • 输入：s = “ABAB”, k = 2

  • 输出：4
    解释：用两个’A’替换为两个’B’,反之亦然。

  • 输入：s = “AABABBA”, k = 1

  • 输出：4
    解释：
    将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。
    子串 “BBBB” 有最长重复字母, 答案为 4。
    可能存在其他的方法来得到同样的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var characterReplacement = function(s, k) {
    let start=0//定义滑动窗口的开始
    let dict={}//定义一个哈希对象
    let numRepeatChar=0//重复字符串的长度
    let longestStr=0//最后的输出结果
    //从左到右遍历字符串
    for(let end=0;end<s.length;++end){
        let c1=s[end]
        dict[c1]=dict[c1]||0
        dict[c1]+=1
        numRepeatChar=Math.max(numRepeatChar,dict[c1])
        if(((end-start+1)-numRepeatChar)>k){
            //开始收缩
            dict[s[start]]--
            start++
        }
        longestStr=Math.max(longestStr,(end-start+1))
    }
    return longestStr
};