难度: Medium
原题连接
内容描述
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Example 1:
Input:
s = "ABAB", k = 2
Output:
4
Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1
Output:
4
Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******
假设我们用来替换别的字符的那个字符是c，那么题目可以转变成这样一个问题，在一个window里面，最多有k个不为c的字符，这样才是满足条件的
那么这样的字符c有哪些呢？毫无疑问是set(s)里面的这些字符。
然后我们维护一个window，不断计算不为c的字符的个数counter，如果counter大于n了说明我们怎么替换也不行了，我们就要将start往前挪一格，否则一直挪end。 每次挪完end之后都要记得更新这一轮的最大长度
每个字符c循环后都要更新最终res。
代码如下：只beats 15%
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
res = 0
for c in set(s):
start, end, counter, length = 0, 0, 0, 0
while end < len(s):
if s[end] != c:
counter += 1
end += 1 # end 永远指向下一个待处理的字符
while counter > k:
if s[start] != c:
counter -= 1
start += 1
length = max(length, end - start) # 因此这里是```end - start```而不是```end - start + 1```
res = max(res, length)
return res思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******
我们不按照可能的字符来遍历了，我们每次维护一个当前的最大字符频率，如果end - start + 1 - max_freq > k我们就知道此时怎么替换都不行了
这个时候我们就要将start往前挪一格，对应的东西全都更新一下
beats 93.46%
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
lookup = {}
start, end, max_freq, res = 0, 0, 0, 0
while end < len(s):
lookup[s[end]] = lookup.get(s[end], 0) + 1
max_freq = max(max_freq, lookup[s[end]])
if end - start + 1 - max_freq > k: # 这里为什么用if不用while呢？见下方解析
lookup[s[start]] -= 1
start += 1
end += 1
res = max(res, end - start)
return res上面用if不用while是因为在接下来的变化当中，我们start肯定是要前进一位的，end和max_freq此时没有变化，那么也就是说
end - start + 1 - max_freq > k在经过一次if后就一定不会再满足了，所以这个地方不用while直接用if即可。