0424：替换后的最长重复字符（★）

2016-02-28 约 636 字预计阅读 2 分钟次阅读

力扣第 424 题

题目

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

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

提示：

1 <= s.length <= 10⁵
s 仅由大写英文字母组成
0 <= k <= s.length

分析

#1

典型的滑动窗口问题，维护窗口内的计数即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res,i = 0,0
        ct = defaultdict(int)
        for j,x in enumerate(s):
            ct[x] += 1
            while j-i+1-max(ct.values())>k:
                ct[s[i]]-=1
                i += 1
            res = max(res,j-i+1)
        return res

140 ms

#2

还有个剪枝技巧：

因为是求最大长度，所以窗口无需缩小，不满足时移动一步即可
窗口不会缩小，那么返回最终窗口大小即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        i,j = 0,0
        ct = defaultdict(int)
        for j,x in enumerate(s):
            ct[x] += 1
            if j-i+1-max(ct.values())>k:
                ct[s[i]]-=1
                i += 1
        return j-i+1

92 ms

#3

还可以优化掉字符种类的时间

上述过程中，窗口有两种变化，一种是右边不断扩大，一种是滑动
注意到每次从滑动状态切换到扩大状态时，一定是新加入的字母 a 为众数
- 否则，假如此时窗口是 [i,j]，字母 b 为满足条件的众数
- 那么对于 [i-1,j]，字母 b 也是满足条件的众数
- 那么上一步的窗口 [i-1,j-1] 就应该扩大，而不是滑动了，矛盾
因此，只要用新加入的字母维护众数个数 ma 即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        i,j = 0,0
        ct = defaultdict(int)
        ma = 0
        for j,x in enumerate(s):
            ct[x] += 1
            ma = max(ma,ct[x])
            if j-i+1-ma>k:
                ct[s[i]]-=1
                i += 1
        return j-i+1

70 ms

目录

0424：替换后的最长重复字符（★）

题目

分析

#1

#2

#3

解答