leetcode_424

发表于   |   分类于

Longest Repeating Character Replacement

题目戳这

题意

给定一个字符串s,有将其中k个字符替换为其他任意字符的机会，求在替换次数不超过k次的条件下字符串能够形成的最长重复子串。

解法

用了滑窗法，用一个大小不定的窗口(窗口大小的限制因素就是k)来圈出一段连续的字符串，然后到此统计出现过最多次数(num)的字符,如果此时需要改变的字符数大于k的时候，则将窗口的左边界往右移动，此时还得将移出窗口的字符从统计里面删去。注意一点，其实移出窗口的字符不一定就是不需要改变的字符，也就是说此时需要改变的字符数并没有变，可能还是大于k，但是注意长度还是一致的，在这里我们并不关心是哪段字符，只要长度对了就行。

比如AAABB,k=1,那么我们如果有窗口移到第一个B的时候，窗口内容为AAAB，此时符合条件，长度为4，当移到第二个B时，窗口内容为AAABB，不符合条件，左窗口要往右移动一个，则窗口内为AABB，此时其实要改变的仍然是2个B，但是此时已经符合条件了，因为长度为4，这跟之前的结果也是一致的，没毛病。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        start = 0
        end = 0
        vis = [0]*30
        slen = len(s)
        mmax = 0
        ans = 0
        for end in range(0,slen):
            p = ord(s[end])-ord('A')
            vis[p] += 1
            mmax = mmax if mmax > vis[p] else vis[p]
            while end-start+1-mmax > k:
                vis[ord(s[start])-ord('A')] -= 1
                start += 1
            ans = max(ans,end-start+1)
        
        return ans