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:

1
2
3
4
5
6
7
8
Input:
s = "ABAB", k = 2
Output:
4
Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

1
2
3
4
5
6
7
8
9
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.

思路

用暴力解法方法会有TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
length = len(s)
if (not length):
return 0
prev = ""
ans = 1
for i in range(length):
if (prev != s[i]):
prev = s[i]
else:
continue
count = 1
attempt = k
j = i + 1
while(j < length):
if (prev == s[j]):
count += 1
else:
if (attempt):
count += 1
attempt -= 1
else:
break
j += 1
if (attempt):
if (attempt <= i):
count += attempt
else:
count += i
if count > ans:
ans = count
return ans

用Slide Window的解法。

考虑用一个stats的数组统计Sliding Window内数组各个字母的数目。窗口每滑倒一个新的状态,stats数组的统计量都会更新一次。这个Sliding Window需要从头滑到尾,从而找出最长的可替换子数组。

算法复杂度是O(26*n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
length = len(s)
stats = [0] * 26
if (not length):
return 0
prev = ""
ans = 0
start = 0
for i in range(length):
ans += 1
cur = s[i]
index = ord(cur) - ord('A')
stats[index] += 1
maximum = max(stats)
if (ans - maximum > k):
stats[ord(s[start]) - ord('A')] -= 1
start += 1
ans -= 1
return ans