Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.



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.

Difficulty: interview

Starter code:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        

Solutions:
class Solution:
     def characterReplacement(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         if s == "":
             return 0
         count = {}
         lo = 0
         hi = 0
         max_letter = 0
         for hi in range(len(s)):
             try:
                 count[s[hi]] += 1
             except:
                 count[s[hi]] = 1
             if count[s[hi]] > max_letter:
                 max_letter = count[s[hi]]
             if max_letter < hi - lo + 1 - k:
                 if max_letter == count[s[lo]]:
                     max_letter -= 1
                 count[s[lo]] -= 1
                 lo += 1
         return hi - lo + 1

class Solution:
     def characterReplacement(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         ls = len(s)
         start, end, max_len = 0, 0, 0
         char_map, cnt, cur_max_char = {}, 0, 0
         while end < ls:
             # print(char_map)
             if s[end] in char_map:
                 char_map[s[end]] += 1
             else:
                 char_map[s[end]] = 1
             cnt += 1
             if char_map[s[end]] > cur_max_char:
                 cur_max_char = char_map[s[end]]
             # invalid
             if cnt - cur_max_char > k:
                 char_map[s[start]] -= 1
                 start += 1
                 cnt -= 1
             else:
                 max_len = max(max_len, cnt)
             end += 1
                 
         return max_len


class Solution:
     def characterReplacement(self, s, k):
         """
         :type s: str
         :type k: int
         :rtype: int
         """
         start = end  = maxn = 0
         alpha_dict = collections.defaultdict(int)
         for end in range(1,len(s)+1):
             alpha_dict[s[end-1]] += 1
             maxn = max(maxn, alpha_dict[s[end-1]])
             if end-start > k+maxn:
                 alpha_dict[s[start]] -= 1
                 start += 1
         return end-start