424. Longest Repeating Character Replacement

https://leetcode.com/problems/longest-repeating-character-replacement/

solution

• 转化为滑动窗口中，窗口里最多有k个其他字符的最长子串

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l = 0
        res = 0
        mydict = collections.defaultdict(int)

        for r in range(len(s)):
            mydict[s[r]] += 1

            while (r - l + 1) - max(mydict.values()) > k:
                if mydict[s[l]] > 0:
                    mydict[s[l]] -= 1
                l += 1

            res = max(res, r - l + 1)
        return res

时间复杂度：O(n) 空间复杂度：O(1)