424. Longest Repeating Character Replacement #

Problem #

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 10^4.

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.

Problem Summary #

Given a string and the number of transformations K, after performing K character transformations, output the maximum length of consecutive identical letters.

Solution Approach #

The author also submitted this problem several times before passing. This problem tests the sliding window technique, but you cannot simply move the left and right windows to the right. Because a case like ABBBBBA may exist, and this case needs to be considered from both directions. The correct sliding window approach should be to count the letter with the highest frequency while sliding, because the final longest length solution must be obtained by changing other letters based on the letter with the highest frequency. During the window sliding process, subtract the length of the most frequent character in the window from the window length. If the difference is greater than K, it means the left window needs to be shrunk until the difference equals K. Continuously take the maximum window length for res.

Code #

package leetcode

func characterReplacement(s string, k int) int {
	res, left, counter, freq := 0, 0, 0, make([]int, 26)
	for right := 0; right < len(s); right++ {
		freq[s[right]-'A']++
		counter = max(counter, freq[s[right]-'A'])
		for right-left+1-counter > k {
			freq[s[left]-'A']--
			left++
		}
		res = max(res, right-left+1)
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}