Longest Repeating Character Replacement

The problem

You are given a string text of uppercase letters and a number max_changes. You may change any letter of text into any other uppercase letter, at most max_changes times in total.

Return the length of the longest substring that can be made of one letter repeated, after those changes. A substring is a run of letters that sit next to each other.

Example 1

Input: text = "AABCBBA", max_changes = 1

Output: 4

Change the C in “BCBB” to a B. That gives “BBBB”, 4 letters long.

text

A0A1B2C3B4B5A6

max_changes

1

Example 2

Input: text = "XYZ", max_changes = 0

Output: 1

No changes are allowed, and no letter repeats, so the best is a single letter.

Example 3

Input: text = "MMNN", max_changes = 2

Output: 4

Change both N’s into M’s, or both M’s into N’s. The whole string becomes one letter.

Constraints

• 1 ≤ n ≤ 100,000, where n is the length of text
• text holds only uppercase English letters, A to Z.
• 0 ≤ max_changes ≤ n

Clarifying questions

Do we have to use all max_changes changes?

No. At most max_changes. Using fewer is fine.

Do we return the new string?

No. Only the length of the longest run we can make.

Which letter should the run be made of?

Any letter. In practice, keep the most common letter of the window and change the rest.

Which letters can appear?

Only A to Z, so 26 counters are enough.

Spot the pattern

For any substring, the cheapest way to make it one letter is to keep its most common letter and change all the others. So a substring works when length − (count of its most common letter) ≤ max_changes. We want the longest contiguous run that obeys a rule, and growing a run never makes the rule easier to meet. That is the sliding window pattern.

Solutions

Brute forceO(n²)Sliding windowO(n)

Show all

This problem has two approaches. Checking every substring from scratch would be O(n³), which is just a slower brute force.

Brute force O(n²)

The idea

Try every start i. Grow the window one letter at a time and keep a count of each letter in it. The window is fine while its length minus its biggest count is at most max_changes. The first time it is not fine, stop: one more letter can add at most 1 to the biggest count, so a longer window needs at least as many changes.

Keep the longest fine window over all starts.

Walkthrough

text

A0A1B2C3B4B5A6

best

0

1. best = 0
2. for i in range(len(text)):
3. count = [0] * 26
4. for j in range(i, len(text)):
5. count[text[j]] += 1
6. if (j - i + 1) - max(count) <= max_changes:
7. best = max(best, j - i + 1)
8. else:
9. break
10. return best

For each start i, grow the window. It is fine while (length − count of its most common letter) ≤ max_changes = 1: that many changes make every letter the same.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: from every start, grow the window while it needs at most maxChanges changes.
    // n starts, up to n steps each, and a 26-letter max per step: O(26 * n^2) = O(n^2).
    public int characterReplacement(String text, int maxChanges) {
        int textLength = text.length();
        int best = 0;
        for (int i = 0; i < textLength; i++) {
            int[] count = new int[26];
            for (int j = i; j < textLength; j++) {
                count[text.charAt(j) - 'A']++;
                // Keep the most common letter; every other letter must change.
                if ((j - i + 1) - max(count) <= maxChanges) best = Math.max(best, j - i + 1);
                // A longer window from i needs at least as many changes.
                else break;
            }
        }
        return best;
    }

    private int max(int[] count) {
        int biggest = 0;
        for (int letterCount : count) biggest = Math.max(biggest, letterCount);
        return biggest;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines add one letter to its count and test the window. They sit inside two loops. The test takes the max over 26 counters, which is 26 steps, but 26 never grows with n. So each run counts as 1 step.

   1. best = 0
   2. for i in range(len(text)):
   3. count = [0] * 26
   4. for j in range(i, len(text)):
   5. count[text[j]] += 1
   6. if (j - i + 1) - max(count) <= max_changes:
   7. best = max(best, j - i + 1)
   8. else:
   9. break
   10. return best

2. 2 Count the runs on Example 1

   Example 1 has 7 letters. The table counts the inner runs for each start, including the run that finds the window is no longer fine and stops.

   4 + 3 + 5 + 4 + 3 + 2 + 1 = 22 runs.

   start i	0	1	2	3	4	5	6
   inner runs	4	3	5	4	3	2	1

   total

   4 + 3 + 5 + 4 + 3 + 2 + 1 = 22

3. 3 Write the count for any n

   In the worst case, like a string of one letter, no window ever stops early. Then start i runs to the end:

   n + (n − 1) + … + 1 = n × (n + 1) / 2 = ½n² + ½n

   Check it with Example 1: a 7-letter string that never stops would take 7 × 8 / 2 = 28 runs. The real 22 is lower because some starts stop early.

4. 4 Keep only the part that grows fastest

   • Drop the +½n and drop the ½. Neither changes how fast the count grows.
   • Drop the 26. The max over 26 counters is a fixed cost per run.

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps 26 counters and a few numbers. That does not grow with n, so the space is O(1).

   count (26 numbers)bestij

Sliding window O(n)

The idea

Keep one window, from left to right, and the count of each letter inside it.

Move right one step at a time and add its letter. Now check the window: if length − (biggest count) > max_changes, it needs too many changes. Shrink it from the left, one letter at a time, until it is fine again. Then measure it.

We never move left backward. That is safe because a window that starts further left and ends at right is longer, so it needs at least as many changes as the one that already failed.

The invariant: after each step, the window is the longest fine window that ends at right.

Walkthrough

text

A0A1B2C3B4B5A6

letter	A	B	C
count in window	0	0	0

best

0

1. count = [0] * 26
2. left = best = 0
3. for right in range(len(text)):
4. count[text[right]] += 1
5. while (right - left + 1) - max(count) > max_changes:
6. count[text[left]] -= 1
7. left += 1
8. best = max(best, right - left + 1)
9. return best

Keep a window and the count of each letter inside it. The window is valid while length − (most common count) ≤ max_changes = 1.

← BackStep →Play1 / 13

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sliding window: grow on the right, shrink on the left while too many changes are needed.
    // Each letter enters and leaves once, with a 26-letter max per step: O(26 * n) = O(n).
    public int characterReplacement(String text, int maxChanges) {
        int[] count = new int[26];
        int left = 0, best = 0;
        for (int right = 0; right < text.length(); right++) {
            count[text.charAt(right) - 'A']++;
            // Keep the most common letter; every other letter must change.
            while ((right - left + 1) - max(count) > maxChanges) {
                count[text.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    private int max(int[] count) {
        int biggest = 0;
        for (int letterCount : count) biggest = Math.max(biggest, letterCount);
        return biggest;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the for loop adds one letter. Each run of the while loop removes one. Both also take a max over 26 counters, a fixed cost, so each run is 1 step. The while sits inside the for, so the question is how often it really runs in total.

   1. count = [0] * 26
   2. left = best = 0
   3. for right in range(len(text)):
   4. count[text[right]] += 1
   5. while (right - left + 1) - max(count) > max_changes:
   6. count[text[left]] -= 1
   7. left += 1
   8. best = max(best, right - left + 1)
   9. return best

2. 2 Count the runs on Example 1

   Example 1 has 7 letters. right moves 7 times. left moves 4 times in total: twice when the C comes in, and twice when the last A comes in.

   7 + 4 = 11 runs.

   pointer	right (adds)	left (removes)
   moves on Example 1	7	4

   total

   7 + 4 = 11 moves, each with a 26-count max

3. 3 Write the count for any n

   right moves n times. left only moves forward and never passes right, so it moves at most n times in total. Each move costs about 26 steps for the max:

   26 × (n + at most n) ≤ 52n

   Check it with Example 1: 11 moves, below 2 × 7 = 14.

4. 4 Keep only the part that grows fastest

   Drop the 52. It is a fixed number, so it does not change how the work grows. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps 26 counters, left, right and best. That is a fixed amount, so the space is O(1).

   count (26 numbers)leftrightbest

Common mistake

Counting the window's letters wrong after shrinking

When left moves, take 1 from the count of the letter that just left the window. Forgetting this keeps old letters in the counts. The window then looks like it needs fewer changes than it does, and the answer comes out too big.

Tested at the limits

2,000 random texts of 1 to 10 letters from A, B and C, with a budget from 0 changes up to the whole length. The brute force and the sliding window gave the same answer every time.

Largest inputs	Result
100,000 letters (the most allowed), mostly A and B, with 1,000 changes allowed, so the window keeps growing and sliding. Sliding window.	0.08 s, and under 0.001 MB of extra memory: just the 26 counters.
2,000 letters, 20 changes. Brute force.	0.03 s. At 100,000 letters it would check about 5 billion windows, which is why the sliding window matters.