Leetcode --- 424. Longest Repeating Character Replacement
===

## Description
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

## Examples

* Ex1:
**Input**: s = "ABAB", k = 2
**Output**: 4
**Explanation**: Replace the two 'A's with two 'B's or vice versa.
* Ex2:
**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.

## Constraints

* 1 <= s.length <= 105
* s consists of only uppercase English letters.
* 0 <= k <= s.length

## Solution

用DP想了一些解，都沒有找到關係，DP無法解

-> Sliding window:
key concept:在window中存的是最多出現的字元x個加上其他字元(可容錯)k個

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:    
        count = collections.Counter()
        l = len(s)
        if k >= l :
            return k
        if l == 1 :
            return l
        left = 0
        max_n =0
        for right in range(l):
            count[s[right]] += 1
            MaxCharInWindow = count.most_common(1)[0][1]
            
            if right -left +1 > MaxCharInWindow + k:
                count[s[left]] -=1
                left +=1
                
            if max_n < right -left +1:
                max_n = right -left +1
                
        return max_n

**collections.Counter():**
是dict的子集，可以對我的dict每一個key的value做加減，其中most_common(n)是返回一個list，裡面以value大小做排行，列出前n個

## Complexity analysis
* Time Complexity:
run過整個字串，每一次最多効正一次O(1)，==O(n)==
* Space compleity:
最多每一個字元不一樣，要allocate==O(n)==

## Submissions
Runtime: 296 ms, faster than 13.83% of Python3 online submissions for Longest Repeating Character Replacement.
Memory Usage: 14.1 MB, less than 94.64% of Python3 online submissions for Longest Repeating Character Replacement.

###### tags: `Leetcode` `String` `sliding window`