## 题目描述：

LeetCode 424. Longest Repeating Character Replacement

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.
```

## Python代码：

``````class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
table = collections.Counter()
res = 0
p1 = p2 = 0
while p2 < len(s):
table[s[p2]] += 1
p2 += 1
while p2 - p1 - max(table.values()) > k:
table[s[p1]] -= 1
p1 += 1
res = max(res, p2 - p1)
return res
``````

## Python代码：

``````class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
sizes = len(s)
letters = set(s)

cdict = collections.defaultdict(list)
li, lc = 0, (s[0] if s else None)
for i, c in enumerate(s):
if c != lc:
cdict[lc].append( (li, i - 1) )
li, lc = i, c
cdict[lc].append( (li, sizes - 1) )

ans = 0
for c in letters:
invs = cdict[c]
ans = max(ans, max(y - x + 1 + min(k, x + sizes - 1 - y) for x, y in invs))
sizec = len(invs)
cnt = k
sp = 0
ep = 1
while sp < sizec and ep < sizec:
if cnt >= invs[ep][0] - invs[ep - 1][1] - 1:
cnt -= invs[ep][0] - invs[ep - 1][1] - 1
lenc = invs[ep][1] - invs[sp][0] + 1 + min(cnt, invs[sp][0] + sizes - 1 - invs[ep][1])
ans = max(ans, lenc)
ep += 1
else:
sp += 1
cnt += invs[sp][0] - invs[sp - 1][1] - 1
return ans
``````

Pingbacks已关闭。