#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 ↗

Approach: Sliding Window

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

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

O(n) O(1)

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