424. Longest Repeating Character Replacement

Medium


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.

 

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.

 

Constraints:

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




 class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l = 0
        mC = 0
        dic = {}

        for r, subS in enumerate(s):
            dic[subS] = 1+dic.get(subS, 0)

            while((r-l+1) - max(dic.values()) > k):
                dic[s[l]] -=1
                l+=1
            mC = max(mC, r-l+1)            
        return mC

Random Note


From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict