Workspace

Problem workspace

3 day streakD

Longest Repeating Character Replacement

MediumSliding WindowLongest windows

The challenge

Return the longest substring length that can become a single repeated letter after replacing at most k characters.

Uppercase English letters; k ≥ 0. Empty input returns 0.

Example

AABABBA, k = 1 → 4: replace the B in AABA to get AAAA.

Use the walkthrough below to inspect the input and each state change.

See Character replacement, step by step

Expand, shrink, and inspect the window state.

7 elements · zero-based indicesk = 1
Sliding window over 7 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1A0A1B2A3B4B5A6
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 20

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

0
View exact input

Input: ["A","A","B","A","B","B","A"] · k = 1

Current window is empty.

Put it into code

Keep the most common letter and replace the rest. This version recomputes the exact maximum frequency so every displayed window is truly valid.

Indices are zero-based. C++ uses C++17 or later.

def character_replacement(s, k):
    # Uppercase English letters. Recompute the exact max count.
    count = [0] * 26
    left = best = 0
    for right, char in enumerate(s):
        count[ord(char) - ord('A')] += 1
        while right - left + 1 - max(count) > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap