← Back to DSA Animator
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.