leetcode424 Longest Repeating Character Replacement

 1 """
 2 Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.
 3 In one operation, you can choose any character of the string and change it to any other uppercase English character.
 4 Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.
 5 Note:
 6 Both the string's length and k will not exceed 104.
 7 Example 1:
 8 Input:
 9 s = "ABAB", k = 2
10 Output:
11 4
12 Explanation:
13 Replace the two 'A's with two 'B's or vice versa.
14 Example 2:
15 Input:
16 s = "AABABBA", k = 1
17 Output:
18 4
19 Explanation:
20 Replace the one 'A' in the middle with 'B' and form "AABBBBA".
21 The substring "BBBB" has the longest repeating letters, which is 4.
22 """
23 class Solution:
24     def characterReplacement(self, s, k):
25         from collections import defaultdict
26         d = defaultdict(int)
27         i = 0
28         count = 0 #!!!存储当前出现字符最多的数量
29         res = 0
30         for j in range(len(s)):
31             d[s[j]] += 1
32             count = max(count, d[s[j]])
33             while j - i + 1 - count > k: #!!!滑动窗口移动关键
34                 d[s[i]] -= 1
35                 count = max(count, d[s[i]])
36                 i += 1
37             res = max(res,j - i + 1)
38         return res