LeetCode 424. 替换后的最长重复字符

Question

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 104。

示例 1：

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

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

最长连续 1 模型

思路

这道题和那两道题差不多。唯一的不同是这道题是 26 种可能（因为每一个大写字母都可能是最终的最长重复子串包含的字母），而上面两题是一种可能。这也不难，枚举 26 种情况，取最大值就行了。

最长连续 1 模型可以直接参考上面的链接。其核心算法简单来说，就是维护一个可变窗口，窗口内的不重复字符小于等于 k，最终返回最大窗口的大小即可。

关键点

• 最长连续 1 模型

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        def fix(c, k):
            ans = i = 0
            for j in range(len(s)):
                k -= s[j] != c
                while i < j and k < 0:
                    k += s[i] != c
                    i += 1
                ans = max(ans, j - i + 1)
            return ans

        ans = 0
        for i in range(26):
            ans = max(ans, fix(chr(ord("A") + i), k))
        return ans

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(26 * n)$
• 空间复杂度：$O(1)$

空间换时间

思路

我们也可以用一个长度为 26 的数组 counts 记录每个字母出现的频率，如果窗口大小大于最大频率+k，我们需要收缩窗口。

这提示我们继续使用滑动窗口技巧。和上面一样，也是维护一个可变窗口，窗口内的不重复字符小于等于 k，最终返回最大窗口的大小即可。

关键点

• 空间换时间

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if not s: return 0
        counts = [0] * 26
        i = most_fraq = 0
        for j in range(len(s)):
            counts[ord(s[j]) - ord("A")] += 1
            most_fraq = max(most_fraq, counts[ord(s[j]) - ord("A")])
            if i < j and j - i + 1 - most_fraq > k:
                counts[ord(s[i]) - ord("A")] -= 1
                i += 1
        return j - i + 1

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(26)$