Longest Repeating Character Replacement

You're given a string s of uppercase English letters and an integer k. You may pick up to k positions in s and change each of those characters to any uppercase letter.

Return the length of the longest substring that can be made of a single repeated letter after at most k changes.

For any substring, the cheapest way to make it one letter is to keep its most common letter and change everything else. So a window of length len is fixable exactly when len - maxCount <= k, where maxCount is how often its most frequent letter appears.

That condition is monotone in the right way for a sliding window: grow the right edge one character at a time, and when the window stops being fixable, move the left edge forward. A neat extra trick: you never need to decrease maxCount when the left edge moves. A stale, too-high maxCount can only keep the window at its current size; it can never let the answer grow past a length that was truly achievable, because the answer only grows when a real new maximum appears.

def character_replacement(s: str, k: int) -> int:
    counts = [0] * 26
    left = 0
    max_count = 0
    for right, ch in enumerate(s):
        idx = ord(ch) - 65
        counts[idx] += 1
        max_count = max(max_count, counts[idx])
        if right - left + 1 - max_count > k:
            counts[ord(s[left]) - 65] -= 1
            left += 1
    return len(s) - left

function characterReplacement(s, k) {
  const counts = new Array(26).fill(0);
  let left = 0;
  let maxCount = 0;
  for (let right = 0; right < s.length; right++) {
    const idx = s.charCodeAt(right) - 65;
    counts[idx]++;
    maxCount = Math.max(maxCount, counts[idx]);
    if (right - left + 1 - maxCount > k) {
      counts[s.charCodeAt(left) - 65]--;
      left++;
    }
  }
  return s.length - left;
}

Start from the fixability test: "keep the most common letter, change the rest, so the window is valid when length minus max count is at most k." Once that's on the board, the sliding window follows.

The stale maxCount trick is the part interviewers like to probe. If you use it, be ready to explain why it's safe. If you're not confident, recompute the max from the 26 counts each step: it's still linear and much easier to defend.