#17 Medium Time O(n) Space O(1) Animated

Longest Repeating Character Replacement

Find the longest substring containing the same letter after at most k replacements.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Sliding window with a maintained constraint

Expand to include new information, then shrink only until the window is valid again.

Approach: Sliding Window

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Expand to include new information, then shrink only until the window is valid again.

Common Pitfall

Update the best answer only when the window satisfies the problem constraint.

Description

Find the longest substring containing the same letter after at most k replacements.

Constraints

Time Complexity: O(n)
Space Complexity: O(1)

Solution — Sliding Window

TimeO(n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Expand the right edge.
Update window state.
Shrink from the left while invalid.
Record the best valid window.

def characterReplacement(s, k):
    count = {}
    res = 0
    
    l = 0
    maxf = 0
    for r in range(len(s)):
        count[s[r]] = count.get(s[r], 0) + 1
        maxf = max(maxf, count[s[r]])
        
        if (r - l + 1) - maxf > k:
            count[s[l]] -= 1
            l += 1
            
        res = max(res, r - l + 1)
    return res

Longest Substring Without Repeating Characters

Permutation in String

Longest Repeating Character Replacement

Steps

Description

Constraints

Tags

Solution — Sliding Window