Longest Repeating Character Replacement

The problem

You are given a string s of uppercase letters and a number k. A replacement changes one character of s into any uppercase letter. Find the longest substring, a run of neighboring characters, that can be turned into a single repeated letter with at most k replacements, and return its length. An empty string returns 0.

What to write

function solve(s: string, k: number): number

Input
s = "AABABBA"
k = 1

Output
4

Input
s = "ABAB"
k = 2

Output
4

Constraints

s contains uppercase English letters; 0 ≤ k ≤ s.length.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Only the 26 uppercase letters appear. The answer is one stretch of neighboring characters, and you are free to choose which letter that stretch becomes. With k = 0 nothing can be replaced, so the answer is then the longest run of one letter.

2. Hint 2: Ask a smaller question

   Take the stretch "AABAB". To turn it into one repeated letter with as few replacements as possible, which letter do you keep, and how many characters do you replace? What is the rule for any stretch?

3. Hint 3: Name the pattern

   A stretch can be turned into one letter when its length minus the count of its most common letter is at most k. You want the longest such stretch, and a letter added on the right or dropped on the left changes one count. Growing on the right and giving up letters on the left is a variable sliding window. Read the lesson on variable sliding window.

4. Hint 4: State the invariant

   After every step, the window's length is at most the highest count seen plus k. The window never gets shorter: each step it either grows by one letter or slides one place to the right. So its length is always the best length found so far.

5. Hint 5: Sketch the pseudocode

   left, top and best start at 0. For each position r: count the letter at r, and keep the highest count seen in top. While r - left + 1 > top + k: lower the count of the letter at left and add 1 to left. Then best = the larger of best and the window's length. Return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Maintain a window and its largest seen character frequency. When the window is longer than that frequency plus k, drop its leftmost character.

The slow way

For every substring, count its letters, find the most common one and check that the others number at most k. It is correct, but a string of n letters has about n × n / 2 substrings, and each one is counted from scratch.

The insight

Call a stretch fixable when at most k replacements turn it into one repeated letter. That holds exactly when its length minus the count of its most common letter is at most k: keep that letter, replace the rest. Only a window longer than the best so far matters, so the window never has to shrink. It grows when the next letter fits, and otherwise slides one place.

Step by step

1. Count the letters in the window and remember the highest count seen. The window is the stretch between a left and a right edge. The highest count is a record: it is raised when a letter beats it and it is never lowered.
2. Add the next letter to the window and update the highest count. Only the new letter's count went up, so it is the only one that can beat the record. One comparison replaces a search through all 26 counts.
3. While length minus highest count is above k, drop the leftmost letter. A window needs at least its length minus the record in replacements, because no letter's real count is above the record. So a window that fails here cannot be fixed. One letter came in, so dropping one is enough.
4. Measure the window and keep the longest length seen. A window that passed the check sets a new best length. After a drop the window keeps its old length and may not be fixable, which is fine: only its length is used.
5. The longest length seen is the answer. The window never got shorter, so the best length is also the window's final length. Each time the window grew, the new letter fit, so that length belongs to a stretch that can be fixed.

The same numbered steps are the comments in each solution.

function solve(s, k) {
  // 1. Count the letters in the window and remember the highest count seen
  const counts = new Map();
  let left = 0,
    best = 0,
    max = 0;
  for (let right = 0; right < s.length; right++) {
    // 2. Add the next letter to the window and update the highest count
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    max = Math.max(max, counts.get(s[right]));
    // 3. While length minus highest count is above k, drop the leftmost letter
    while (right - left + 1 - max > k) {
      counts.set(s[left], counts.get(s[left]) - 1);
      left++;
    }
    // 4. Measure the window and keep the longest length seen
    best = Math.max(best, right - left + 1);
  }
  // 5. The longest length seen is the answer
  return best;
}

function solve(s: string, k: number): number {
  // 1. Count the letters in the window and remember the highest count seen
  const counts = new Map<string, number>();
  let left = 0,
    best = 0,
    max = 0;
  for (let right = 0; right < s.length; right++) {
    // 2. Add the next letter to the window and update the highest count
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    max = Math.max(max, counts.get(s[right])!);
    // 3. While length minus highest count is above k, drop the leftmost letter
    while (right - left + 1 - max > k) {
      counts.set(s[left], counts.get(s[left])! - 1);
      left++;
    }
    // 4. Measure the window and keep the longest length seen
    best = Math.max(best, right - left + 1);
  }
  // 5. The longest length seen is the answer
  return best;
}

def solve(s, k):
    # 1. Count the letters in the window and remember the highest count seen
    counts = {}
    left = best = max_count = 0
    for right, char in enumerate(s):
        # 2. Add the next letter to the window and update the highest count
        counts[char] = counts.get(char, 0) + 1
        max_count = max(max_count, counts[char])
        # 3. While length minus highest count is above k, drop the leftmost letter
        while right - left + 1 - max_count > k:
            counts[s[left]] -= 1
            left += 1
        # 4. Measure the window and keep the longest length seen
        best = max(best, right - left + 1)
    # 5. The longest length seen is the answer
    return best

Example 1, traced

Input
s = "AABABBA"
k = 1

Output
4

Why it works

No letter's real count is above the record, so a window that fails the check cannot be fixed. The left edge therefore never shortens a fixable window. A window that grows is fixable too. Until a letter leaves, the record is exact. After that the window is as long as the record allows, so it grows only when a letter sets a new record, which is exact again.

Time and space

Time O(n), extra space O(1). The right edge takes in each of the n letters once. The left edge only moves forward, at most n times in all. So the time is O(n). The counts never hold more than 26 letters, whatever the length of the string: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Measure the window after the left edge has moved, not before. Measured first, a window that holds one letter too many gets counted, and example 1 gives 5 instead of 4.
• When the left edge moves, lower the count of the letter that leaves. If you forget, the counts go on describing letters that are no longer in the window, and example 1 gives 5 instead of 4.
• The window is too big only when it needs more than k replacements. Testing for k or more throws away windows that use all k: example 1 gives 2 instead of 4.

Pattern

Variable sliding window. Builds on Valid Anagram and Longest Substring Without Repeating Characters.

Keep going