progress

~/problems / Sliding window

Longest Repeating Character Replacement

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~25 min

Write character_replacement(s: str, k: int) -> int.

s contains only uppercase letters A-Z. You may change at most k characters of s into any other uppercase letter. Return the length of the longest contiguous block of identical letters you can end up with.

Example: s = "BAAB", k = 1 gives 3 (change one B to get "AAAB" or "BAAA"). s = "ABCDE", k = 0 gives 1. s = "AABABBA", k = 1 gives 4.

Constraints: 1 <= len(s) <= 2 * 10^5, 0 <= k <= len(s).

⭐ Bonus: trying every substring still passes; a speed test earns a star in O(n) (O(26·n) is fine).

Show hint

a block can be made uniform when its length minus the count of its most common letter is at most k. Look at contiguous blocks that grow on the right and shrink on the left only when they stop qualifying.

Topic: Sliding window. Grow right, shrink left while invalid; monotonic deque for window max/min.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc