Leetcode 424 python 解题报告

参考了http://www.cnblogs.com/reboot329/p/5968393.html的解题思路

AC代码：

import string
class Solution(object):
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        window = 1
        dict = {}
        for i in string.uppercase:
            dict[i] = 0
        maxj = 0
        l = 0
        ans = 0
        #print dict
        for j in range(len(s)):
            dict[s[j]] += 1
            #print dict
            maxj = max(maxj,dict[s[j]])
            window = j-l+1
            if(window - maxj <= k):
                ans = max(ans, window)
            else:
                dict[s[l]] -= 1
                l += 1

        return ans

      

解题思路：使用滑动窗口，条件是保证在当前窗口大小的情况下，窗口减去窗口中出现最多的字母小于等于k，在符合该条件的前提下，记录下窗口最大时的大小即可，否则向左滑动窗口。向左滑动窗口时，统计的词典中，滑过的字母需减一，向右滑动则加一。