Longest Repeating Character Replacement

LeetCode 424 • Medium • Sliding Window

Input: s = "AABABBA", k = 1 → Output: 4
Replace at most k characters so the substring has all the same letter. Find the longest such substring.

TimeO(n)single pass

SpaceO(1)26-char map

Window: 0 Max Freq: 0 Best: 0

Window

Right (expand)

Shrink

Result

Window

—

Counts

—

Result

pending

Speed:

Ready

Press Play to watch the sliding window expand and contract, or Step to advance one operation.
The window grows right, and shrinks from the left when replacements exceed k.

✎ Whiteboard

Size:3

⌨ Type It — Sliding Window

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ CHARACTER REPLACEMENT — SLIDING WINDOW ═══

PATTERN ▸ Expand right, shrink left O(n) · O(1)

① SETUP

count = {}

left = 0, max_count = 0, result = 0

② EXPAND — RIGHT POINTER

for right in range(len(s)):

count[s[right]] += 1

max_count = max(max_count, count[s[right]])

③ SHRINK — WINDOW INVALID

while (right - left + 1) - max_count > k:

count[s[left]] -= 1

left += 1

④ UPDATE RESULT

result = max(result, right - left + 1)

⑤ RETURN

return result

Vars: count, left, right, max_count, result

▼ your implementation ▼

Verify your solution:

⌨ Type It — Recursive

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ CHARACTER REPLACEMENT — RECURSIVE ═══

PATTERN ▸ Recursive sliding window O(n) · O(n)

① DEFINE HELPER

def helper(right, left, count, max_count, result):

② BASE CASE

if right == len(s): return result

③ EXPAND + SHRINK

count[s[right]] += 1

max_count = max(max_count, count[s[right]])

while (right-left+1) - max_count > k:

count[s[left]] -= 1; left += 1

④ RECURSE

result = max(result, right - left + 1)

return helper(right+1, left, count, max_count, result)

⑤ ENTRY

return helper(0, 0, {}, 0, 0)

▼ your implementation ▼

Verify your solution: