第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0424. 替换后的最长重复字符

题目地址(424. 替换后的最长重复字符)

题目描述

1
给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。
2
3
注意:字符串长度 和 k 不会超过 104。
4
5
6
7
示例 1:
8
9
输入:s = "ABAB", k = 2
10
输出:4
11
解释:用两个'A'替换为两个'B',反之亦然。
12
13
14
示例 2:
15
16
输入:s = "AABABBA", k = 1
17
输出:4
18
解释:
19
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
20
子串 "BBBB" 有最长重复字母, 答案为 4。
Copied!

前置知识

-

公司

  • 暂无

最长连续 1 模型

思路

这道题其实就是我之前写的滑动窗口的一道题【1004. 最大连续 1 的个数 III】滑动窗口(Python3)的换皮题。字节跳动2018 年的校招(第四批)也考察了这道题的换皮题。
这道题和那两道题差不多。唯一的不同是这道题是 26 种可能(因为每一个大写字母都可能是最终的最长重复子串包含的字母),而上面两题是一种可能。这也不难,枚举 26 种情况,取最大值就行了。
最长连续 1 模型可以直接参考上面的链接。其核心算法简单来说,就是维护一个可变窗口,窗口内的不重复字符小于等于 k,最终返回最大窗口的大小即可。

关键点

  • 最长连续 1 模型

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def characterReplacement(self, s: str, k: int) -> int:
3
def fix(c, k):
4
ans = i = 0
5
for j in range(len(s)):
6
k -= s[j] != c
7
while i < j and k < 0:
8
k += s[i] != c
9
i += 1
10
ans = max(ans, j - i + 1)
11
return ans
12
13
ans = 0
14
for i in range(26):
15
ans = max(ans, fix(chr(ord("A") + i), k))
16
return ans
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(26 * n)$
  • 空间复杂度:$O(1)$

空间换时间

思路

我们也可以用一个长度为 26 的数组 counts 记录每个字母出现的频率,如果窗口大小大于最大频率+k,我们需要收缩窗口。
这提示我们继续使用滑动窗口技巧。和上面一样,也是维护一个可变窗口,窗口内的不重复字符小于等于 k,最终返回最大窗口的大小即可。

关键点

  • 空间换时间

代码

  • 语言支持:Python3
Python3 Code:
1
class Solution:
2
def characterReplacement(self, s: str, k: int) -> int:
3
if not s: return 0
4
counts = [0] * 26
5
i = most_fraq = 0
6
for j in range(len(s)):
7
counts[ord(s[j]) - ord("A")] += 1
8
most_fraq = max(most_fraq, counts[ord(s[j]) - ord("A")])
9
if i < j and j - i + 1 - most_fraq > k:
10
counts[ord(s[i]) - ord("A")] -= 1
11
i += 1
12
return j - i + 1
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(26)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。