MediumHash TableStringSliding Window

Longest Repeating Character Replacement

1 approach, code in every language

Given a string s of uppercase English letters and an integer k, you may choose at most k positions and overwrite each with any uppercase letter of your choice. Return the length of the longest substring that can be made into a single repeated letter after those changes.

You do not have to use all k changes.

Example 1

Input: s = "ABAB", k = 2

Output: 4

Change the two B's into A's (or the two A's into B's) to make the whole string uniform.

Example 2

Input: s = "AABABBA", k = 1

Output: 4

One change turns a window like "AABA" into "AAAA", giving a run of length four.

Constraints

1 <= s.length <= 10^5
0 <= k <= s.length
s consists of uppercase English letters only.

Sliding window on replacement budget

Grow a window while the number of characters that differ from its most frequent letter stays within k, tracking the widest valid window.

Loading animation…

Intuition

For any window, the cheapest way to make it uniform is to keep its most frequent letter and rewrite the rest, which costs (window length minus that top frequency) changes. A window is affordable when that cost is at most k. Expanding the right edge and only nudging the left edge forward when the cost exceeds k keeps the window at the largest width achieved so far, so the best length never needs to be recomputed by shrinking eagerly.

Algorithm walkthrough

1Track counts of each letter in the current window and the highest single-letter frequency seen.
2Advance the right edge, updating the count and the running maximum frequency.
3If window length minus the max frequency exceeds k, move the left edge forward and decrement its count.
4Update the best length with the current window width after each step.
5Return the best width once the whole string has been processed.

Implementation

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0] * 26
        left = 0
        max_freq = 0
        best = 0
        base = ord('A')
        for right, ch in enumerate(s):
            idx = ord(ch) - base
            count[idx] += 1
            max_freq = max(max_freq, count[idx])
            while (right - left + 1) - max_freq > k:
                count[ord(s[left]) - base] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Time

O(n)

Space

O(1)

The frequency table has a fixed 26 entries for uppercase letters.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Longest Repainted Stretch is our own problem on the technique behind Longest Repeating Character Replacement: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free