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: Changing the C to A makes indices 1 to 5 read AAAAA. Both six-letter windows hold a B and the C, so they need two changes.

Input: s = "AABBBAB"k = 2
Output: 6
Explanation: Indices 1 to 6 hold ABBBAB, and changing both A letters gives BBBBBB. The whole string has only four B letters among seven, so it needs three changes.

Follow-up

What changes if s can hold any character instead of the 26 uppercase letters?

Hints

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

0 of 3 opened

Solution

Keep a substring's most common letter and change the rest: a substring of length len whose top letter appears top times needs len - top changes. A sliding window finds the longest substring with len - top ≤ k in one pass, because the window never has to shrink and top never has to go down.

Check every substring

Correct, but does not finish on the largest tests

Intuition

For each start, grow the end one letter at a time, update a count per letter and top, and test len - top ≤ k. Each new substring costs one update instead of a fresh count, and every substring gets checked, so the longest reachable one cannot be missed.

A string of length n has about n²/2 substrings: 1.25 × 10^9 checks for n = 5 × 10^4.

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, store the 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

Choose the final letter first. If the run ends up all A, you want the longest substring with at most k letters that are not A.

Move right over the string and count the non-target letters in the window. When the count passes k, move left forward until it is back to k. A window that is too expensive stays too expensive when it grows, so left never moves back, and for each right the window is the longest good one ending there.

Run it for all 26 letters and keep the best: 26 linear passes over up to 5 × 10^4 letters. It stays O(n) 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, subtracting one 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

Keep 26 counts for the window and top, the highest count. When adding s[right] makes the window too expensive, drop one letter on the left: the window slides and keeps its length, since only a longer window can beat the record. Otherwise it grows by one. Its length is always the best so far, so the answer is n - left.

When a letter leaves, leave top alone, even if it is now higher than the real count. After a slide the length is exactly top + k, so growing needs some letter to appear top + 1 times, and top rises with it at that moment. A stale top can only make the window slide, and a slide cannot lose the record.

In BAAACAB with k = 1, BAAAC needs 2 changes and slides to AAAC. The next A raises top to 4 and the window grows to AAACA, length 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, remove s[left] from the counts and move left one step. Never lower top.
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

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 changing the C joins two runs into 5.
Counting changes against the window's first letter instead of its most common one. BAAA needs one change, not three.
Returning n - left from a loop that shrinks the window with while and recomputes the real maximum. That window gets shorter, so keep a separate best.
Measuring the window as right - left. Both ends are inside it, so add one.

Frequently asked questions3

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.

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, no character may repeat, so the window shrinks until the repeat is gone. Here, the length minus the top count must be at most k, so the window can slide at a fixed length.

Can this problem be solved with binary search?

Yes. If a 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.

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

Test #1

Test #2

Test #3

Arguments

s = "BAAACAB"
k = 1

Expected Output

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 questions3

Similar problems