LC424 - Longest Repeating Character Replacement

Problem

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

Input: s = "ABAB", k = 2

Output: 4

Explanation: Replace the two 'A's with two 'B's or vice versa.

Solution

Time complexity is $O(n)$.

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

	count = {}
	maxLen = 0 

	left = 0
	for right in range(len(s)):
		count[s[right]] = 1 + count.get(s[right], 0)

		while (right - left + 1) - max(count.values()) > k:
			count[s[left]] -= 1
			left += 1

		maxLen = max(maxLen, right - left + 1)
	return maxLen