Longest Repeating Character Replacement

Medium

The problem

Given a string s of capital letters and a number k, you may change at most k characters of s into any capital letter. Return the length of the longest piece of the string (a substring) in which all the letters can be made the same.

Example 1
Input: s = "ABAB", k = 2
Output: 4
Change the two B's into A's to get "AAAA".
Example 2
Input: s = "AABCCCD", k = 1
Output: 4
Change the B into C: the piece "BCCC" becomes "CCCC", length 4.
Example 3
Input: s = "ABC", k = 0
Output: 1
No changes allowed, so the best is a single letter.

Limits

1 ≤ s.length ≤ 100,000
s contains only capital letters A to Z
0 ≤ k ≤ s.length

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A window is fixable if (length − count of its most common letter) ≤ k.

The idea

Expand right, count letters, track the max frequency in the window; while length − maxFreq > k shrink left. Answer is the largest window.

Target: O(n) time, O(26) space

Go function shape

func characterReplacement(s string, k int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// CharacterReplacement: a window is fixable when (length - count of its most common letter) <= k.
// maxFreq never needs to shrink: the window only grows when a new record frequency is set.
func CharacterReplacement(s string, k int) int {
	var count [26]int
	best, maxFreq, left := 0, 0, 0
	for right := 0; right < len(s); right++ {
		count[s[right]-'A']++
		maxFreq = max(maxFreq, count[s[right]-'A'])
		for (right-left+1)-maxFreq > k { // more replacements needed than allowed: shrink
			count[s[left]-'A']--
			left++
		}
		best = max(best, right-left+1)
	}
	return best
}

Read the lesson: Sliding Window