Longest Repeating Character Replacement

+10

You get a string s of uppercase English letters and an integer k. You may pick at most k positions of s and change the letter at each one to any other uppercase letter.

Return the length of the longest substring, a run of letters that sit next to each other, that holds a single repeated letter after your changes.

Function

characterReplacement(s: string, k: integer) → integer

sstring: the string of uppercase letters
kinteger: the most letters you may change
Returnsinteger: the length of the longest substring of one repeated letter you can make

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s holds only uppercase English letters.
0 ≤ k ≤ s.length

Examples

Input: s = "BAAACAB"k = 1
Output: 5
Explanation: Change the C to an A and indices 1 to 5 read AAAAA. Six letters would need two changes: indices 0 to 5 hold a B and the C, and indices 1 to 6 hold the C and the last B.

Input: s = "AABBBAB"k = 2
Output: 6
Explanation: In ABBBAB, indices 1 to 6, the two As are the only letters that are not B, so two changes give BBBBBB. The whole string holds three As and four Bs, so it needs three changes.

+17 hidden tests on Submit

Follow-up

What changes if s can hold any character, not only the 26 uppercase letters?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The cost of one substring is plain to see: its length minus the count of its most common letter. The hard part is not paying for all n² substrings. A sliding window reads the string once, and the best version rests on two facts: the window never has to shrink, and the highest letter count never has to go down.

Check every substring

Correct, but does not finish on the largest tests

Intuition

Fix one substring. Which letter should it become? The one that already appears most often, because every other letter has to change. So a substring of length len whose most common letter appears top times needs len - top changes, and it is reachable when that is at most k.

Try every substring. For each start, grow the end one letter at a time and keep a count per letter, raising top as you go. Each new substring then costs one update instead of a fresh count. Every substring gets checked, so the longest reachable one cannot be missed.

It is slow because a string of length n has about n²/2 substrings. For n = 5 × 10^4 that is 1.25 × 10^9 checks, far more than the time limit allows.

Algorithm

Set best to 0.
For every start index, reset the 26 counts and top to 0.
Move end from the start to the last index. Add s[end] to its count, and raise top if that count is now the highest.
If end - start + 1 - top ≤ k, the substring is reachable: store its length if it beats best.
Return best.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

One sliding window per target letter

Intuition

Turn the question around and choose the letter first. If the final run is all A, the question becomes: what is the longest substring with at most k letters that are not A? That is a classic sliding window.

Move right over the string and count the letters inside the window that are not the target. When that count goes over k, move left forward until it is back to k. Growing a window can only add letters to change, so a window that is too expensive stays too expensive when it grows, and left never has to move back. For each right, the window you keep is the longest good one that ends there.

Run this for all 26 letters and keep the best length. Each run is O(n), so the total is 26 passes, about 1.3 × 10^6 steps for n = 5 × 10^4. That is linear, but it reads the string 26 times and works only because the alphabet is small.

Algorithm

For each target letter from A to Z, start a window with left = 0 and others = 0.
Move right over the string. If s[right] is not the target, add one to others.
While others > k, move left forward, and subtract one from others when the letter that leaves is not the target.
Store right - left + 1 if it beats best.
After all 26 letters, return best.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

One window that never shrinks

Intuition

Handle every letter in one window. Keep a count for each of the 26 letters inside it, and top, the highest count. The window needs length - top changes, so it is good while that is at most k.

First fact: the window never has to shrink. You only care about beating the best length found so far, so when adding s[right] makes the window too expensive, drop one letter on the left. The window slides one step and keeps its length. When the window is not too expensive, it grows by one. Its length is therefore always the best length found so far, and at the end the answer is n - left.

Second fact: top never has to go down. When a letter leaves on the left, you leave top alone, so it can be higher than the real count inside the window. That is safe. After a slide the window's length is exactly top + k, so growing it needs a letter that appears top + 1 times inside the window, and at that moment top rises with it. A stale top can make the window slide, never grow by mistake, and sliding does not lose anything, because only a longer window could beat the record.

In BAAACAB with k = 1, the window grows to BAAA and then BAAAC needs 2 changes, so it slides to AAAC. Adding the next A raises top to 4 and the window grows to AAACA, length 5. The last B makes it slide once more, so the answer is 5.

Algorithm

Keep 26 counts, left = 0 and top = 0.
Move right over the string: add s[right] to its count, and raise top if that count is now higher.
If right - left + 1 - top > k, the window needs too many changes: remove s[left] from the counts and move left one step. The window slides and keeps its length.
Never lower top when a letter leaves.
Return the final window length, n - left.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

Pitfalls and edge cases

The window code is short, so most wrong answers come from the cost formula or from a shortcut that only looks right.

Adding k to the longest run. In AAAB with k = 3 that gives 6, longer than the string. In BAAACAB with k = 1 it gives 4, but the right change sits in the middle and joins two runs into 5.
Counting changes against the first letter of the window instead of its most common letter. The window BAAA needs one change, not three.
Returning n - left from a version whose window can shrink. That shortcut holds only when the window never gets shorter, as in the one-window code here. If your loop shrinks the window with while and recomputes the real maximum, keep a separate best.
Measuring the window as right - left. Both ends are inside it, so add one.
Treating k = 0 as a special case. With no changes the window rule already returns the longest run of one letter.

Frequently asked questions4

What is the time complexity of Longest Repeating Character Replacement?

The one-window solution runs in O(n) time, where n is the length of s: right visits each letter once and left moves at most once per step. It uses O(1) extra space, 26 counts and a few integers.

Why does the max frequency not need to be updated when the window slides?

The window is only trying to beat its own record. After a slide its length is top + k, so a longer good window needs some letter to appear more than top times, and that raises top anyway. A top that is too high only keeps the window at its length; it never makes it grow when it should not.

How is this different from Longest Substring Without Repeating Characters?

Both move two edges over the string, but the rule for a good window differs. There, a window is good when no character repeats, and it must shrink until the repeat is gone. Here, a window is good when its length minus its top letter count is at most k, which lets the window slide at a fixed length instead of shrinking.

Can this problem be solved with binary search?

Yes. If some substring of length L is reachable, so is every shorter one inside it, so you can binary search on L. For each L, slide a fixed window of that length and check whether any position needs at most k changes. That is O(n log n), slower than the one-window solution but a fair answer to give.

Python

def characterReplacement(s, k):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "BAAACAB"
k = 1

Expected

Longest Repeating Character Replacement

Function

Constraints

Examples

Hints

Solution

Check every substring

One sliding window per target letter

One window that never shrinks

Pitfalls and edge cases

Frequently asked questions4

Similar problems