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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Amortized analysis

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

Solutions:
class Solution:

	def characterReplacement(self, s, k):
		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):
		ls = len(s)
		(start, end, max_len) = (0, 0, 0)
		(char_map, cnt, cur_max_char) = ({}, 0, 0)
		while end < ls:
			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]]
			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):
		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