DSA AnimatorDSA animations
Longest Repeating Character Replacement LC #424 Medium Sliding Window
Problem

Given a string s and integer k, return the length of the longest substring containing the same letter after replacing at most k characters.

Example 1
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace both A's or both B's → entire string becomes one letter.
Example 2
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace one B in "AABA" → "AAAA" (length 4).
Constraints: 1 ≤ s.length ≤ 10⁵ · s consists of uppercase English letters · 0 ≤ k ≤ s.length
Try Examples
Custom:
Approach
Sliding window — expand r, shrink l when replacements exceed k
Track char frequencies in the window. Replacements needed = windowSize − maxFreq. If that > k, slide left once. Track the largest valid window in maxLen. O(n) time, O(1) space.
String Window
[l .. r]
l (left)
r (right)
window [l..r]
Replacement Formula
windowSize
—
−
maxFreq
—
=
replace
—
replacements = windowSize − maxFreq
Dominant char
—
Most frequent letter in current window
Variables
l
0
r
—
maxFreq
0
replace
—
maxLen
0
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init l = 0, maxFreq = 0, maxLen = 0, freq[26]
2
For each r: expand window — increment freq[s[r]], update maxFreq
3
If (r−l+1) − maxFreq > k → shrink: decrement freq[s[l]], l++
4
maxLen = max(maxLen, r−l+1) — track best valid window
5
Return maxLen
Time
O(n)
Space
O(1)
Why This Works

In any window, windowSize − maxFreq is the minimum replacements needed to make every character the same (keep the dominant letter, change the rest). If that exceeds k, the window is invalid — slide l right once. Each r only moves forward, and l only catches up, so the scan is O(n). maxFreq only increases (an optimization); the window may temporarily be invalid before shrinking, but maxLen records the largest valid window ever seen.

How to solve Longest Repeating Character Replacement

LeetCode 424 · Medium · Strings · Pattern: Sliding Window

Why the obvious approach is slow

Trying every substring and every letter is very expensive. We want one pass.

The key idea

In a window, keep the most frequent letter, and change the rest. So the changes needed are the window length minus the max frequency. If that is more than k, the window is invalid. Then drop one character from the left, and slide forward. The max frequency never needs to go down, because the answer only grows when it grows.

Remember

Changes needed equal window length minus the top count. The window slides, and never shrinks by more than one.

Run the animation above on your own input, or watch the 1:41 video explanation of Longest Repeating Character Replacement with a dry run and Java code.

More Strings problems