424. Longest Repeating Character Replacement

You may change at most k characters of s to any other uppercase letter. Return the length of the longest substring made of a single repeated letter you can get.

Grow the window on the right. If it would need more than k replacements (length − max count > k), slide the left edge forward. maxCount never has to decrease: only a larger maxCount can produce a longer answer.

1function characterReplacement(s: string, k: number): number {
2  const count = new Map<string, number>();
3  let lo = 0, maxCount = 0, best = 0;
4  for (let hi = 0; hi < s.length; hi++) {
5    count.set(s[hi], (count.get(s[hi]) ?? 0) + 1);
6    maxCount = Math.max(maxCount, count.get(s[hi])!);
7    if (hi - lo + 1 - maxCount > k) {
8      count.set(s[lo], count.get(s[lo])! - 1);
9      lo++;
10    }
11    best = Math.max(best, hi - lo + 1);
12  }
13  return best;
14}

s

Empty window.

1 / 0

Space: play/pause · ←/→: step