Longest Repeating Character Replacement

You are given a string s of uppercase English letters and an integer k. You may perform at most k edits, where each edit overwrites one character of s with any uppercase letter.

Return the length of the longest substring that can be made to consist of a single repeated letter after your edits.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length <= 105
• s consists only of uppercase English letters
• 0 <= k <= s.length

Pattern Path · Sliding Window · problem 54 of 169

Start simple

Check every substring, counting its letters to see whether length minus the top count is at most k: O(n²) time even with incremental counts.

The key idea

A substring can be turned into one repeated letter with length - maxCount edits, where maxCount is the frequency of its most common letter. So we want the longest window with length - maxCount <= k.

Slide a window over s while keeping a count of each letter in it. Add s[right], update maxCount, and if the window now needs more than k edits, drop s[left] and advance left. Record the window length after each step.

The subtle part is that maxCount is never recomputed when letters leave. That is safe: the answer is at most maxCount + k, so a window longer than the best so far can only appear when some letter's count rises above the old maxCount, and that rise is detected the moment it happens. A stale, too-large maxCount can only keep the window at its current length, never report a length that was not achieved earlier. Each index enters and leaves the window once, giving linear time with a 26-entry table.

Complexity

• Time: O(n)
• Space: O(1) (26 letter counts)

Python

from collections import Counter

class Solution:
    def characterReplacement(self, s, k):
        counts = Counter()
        max_count = 0  # highest single-letter count seen in any window
        left = 0
        best = 0
        for right, ch in enumerate(s):
            counts[ch] += 1
            max_count = max(max_count, counts[ch])
            # Too many letters to overwrite: shrink from the left.
            while (right - left + 1) - max_count > k:
                counts[s[left]] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

JavaScript

var characterReplacement = function(s, k) {
  const counts = new Array(26).fill(0);
  let maxCount = 0; // highest single-letter count seen in any window
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s.charCodeAt(right) - 65;
    counts[c]++;
    maxCount = Math.max(maxCount, counts[c]);
    // Too many letters to overwrite: shrink from the left.
    while (right - left + 1 - maxCount > k) {
      counts[s.charCodeAt(left) - 65]--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
};

What the interviewer is checking

This checks whether you can phrase a validity condition for a window (length minus top frequency) and defend why the lazily maintained maximum still gives the right answer.

Mistakes to avoid

• Rescanning all 26 counts or recomputing the maximum on every shrink; correct but slower and a sign the invariant is not understood.
• Assuming you must pick which letter to keep ahead of time; the window decides it.
• Returning maxCount + k directly, which can exceed the string length.
• Off-by-one in the window length (right - left + 1).

Follow-ups to expect

• What if the alphabet were all of Unicode? (Hash map of counts; same idea.)
• Return the substring itself, not just its length. (Remember the best window's start.)
• What if only one specific letter may be the target? (Count the other letters instead.)

In real software

Finding the longest stretch of a signal or log that is uniform up to a small number of glitches, for example the longest period a sensor reported one state while tolerating k outlier readings.

Practice next