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