Sliding Window — Longest Repeating Character Replacement
↗ LeetCode: Longest Repeating Character Replacement · Medium · pattern chapter →
Given s (uppercase A–Z) and integer k, return the length of the longest substring you can make of a single repeated character by replacing at most k other characters.
Example 1 — s = "ABAB", k = 2 → 4 (replace both As or both Bs) Example 2 — s = "AABABBA", k = 1 → 4 (window AABA → replace one A with B, or the reverse) Example 3 — s = "AAAA", k = 0 → 4 (already all same)
Constraints — 1 ≤ n ≤ 10⁵, 0 ≤ k ≤ n. Brute is O(n²·26) ≈ 2.6·10¹¹ ops at n=10⁵ (TLE). Sliding window (max-freq + k) is O(n·26) ≈ 2.6·10⁶ ops.
Interview timer00:00
Approach 1 — Try every substring
Intuition. For each s[i..j], count the most frequent letter maxFreq; the window is valid iff (j - i + 1) - maxFreq ≤ k. Track the longest.
int characterReplacementBrute(String s, int k) {
int n = s.length(), best = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {
int[] cnt = new int[26], maxFreq = {0};
for (int p = i; p <= j; p++) {
cnt[s.charAt(p) - 'A']++;
maxFreq[0] = Math.max(maxFreq[0], cnt[s.charAt(p) - 'A']);
}
if (j - i + 1 - maxFreq[0] <= k) best = Math.max(best, j - i + 1);
}
return best;
}Complexity — Time O(n³); Space O(1).
Approach 2 — Sliding window with "lazy" maxFreq
Insight from brute. The window validity check windowLen - maxFreq ≤ k is monotone in one direction: growing right can only require larger maxFreq (or the same) to keep the window feasible. Grow right; if the window becomes invalid, shrink left by exactly one.
Trap — we don't need to recompute maxFreq when shrinking. Any window with size ≤ current best can't improve the answer regardless of stale maxFreq. So we lazily keep the max ever seen.
int characterReplacement(String s, int k) {
int[] cnt = new int[26];
int left = 0, maxCount = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
cnt[s.charAt(right) - 'A']++;
maxCount = Math.max(maxCount, cnt[s.charAt(right) - 'A']);
if (right - left + 1 - maxCount > k)
cnt[s.charAt(left++) - 'A']--;
best = Math.max(best, right - left + 1);
}
return best;
}Complexity — Time O(n); Space O(1) (26 buckets).
Why "lazy max" is safe. The answer we output is never smaller than best. If maxCount is stale (real max is lower), the window only grows if a new character bumps maxCount higher — which is real, not stale. Correctness preserved.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Try every substring | O(n³) | O(1) | baseline; TLE at n=10⁵ |
| Sliding window + lazy maxFreq | O(n) | O(1) | expected optimum |
When to use which
- First pass — state brute, then jump to sliding window.
- "At most k operations" signal → try replacing
maxFreqwith the constrained quantity in the validity formula. - "What if alphabet is Unicode?" → replace
int[26]withHashMap<Character,Integer>; recomputing max on every shrink is O(σ) — slower but still correct. - Follow-up: return the actual substring → track
(bestL, bestLen)and slice.
Related problems
- Longest Substring with At Most K Distinct Characters — sibling
≤ k distinctvariant - Max Consecutive Ones III — binary version
- Replace the Substring for Balanced String — window on outside counts
- Longest Substring Without Repeating Characters — the seed