Sliding Window — Replace the Substring for Balanced String
↗ LeetCode: Replace the Substring for Balanced String · Medium · pattern chapter →
String of Q,W,E,R (length n divisible by 4). Return length of smallest substring to replace so each letter appears n/4 times.
Example 1 — s="QWER" → 0Example 2 — s="QQWE" → 1Example 3 — s="QQQW" → 2
Constraints — 1 ≤ n ≤ 10⁵. Brute try every window is O(n²). At 10⁵ that's 10¹⁰ ops = TLE. Sliding window is O(n) = 10⁵.
Interview timer00:00
Approach 1 — Brute enumerate every window
Intuition. For each (l, r) pair, check whether the outside of the window has each letter ≤ n/4. Return the smallest valid length.
Complexity — Time O(n²) (n² windows × O(1) check with prefix counts); Space O(n). TLE past 10⁴. In an interview say "shrinkable — grow right, shrink left while balanced → O(n)."
Approach 2 — Sliding window over "outside" counts (canonical)
Insight. Substring [l, r] is a valid replacement window iff outside it, no letter exceeds n/4. Shrink l while condition holds; track min length.
int balancedString(String s) {
int n = s.length(), k = n / 4;
int[] cnt = new int[128];
for (char c : s.toCharArray()) cnt[c]++;
int l = 0, best = n;
for (int r = 0; r < n; r++) {
cnt[s.charAt(r)]--;
while (l < n && cnt['Q'] <= k && cnt['W'] <= k && cnt['E'] <= k && cnt['R'] <= k) {
best = Math.min(best, r - l + 1);
cnt[s.charAt(l++)]++;
}
}
return best;
}Complexity — Time O(n); Space O(1). Say aloud in an interview: "inversion trick — instead of tracking the window's contents, track the outside's contents. Same shape as Longest Repeating Character Replacement."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute enumerate windows | O(n²) | O(n) | Reference; TLE past 10⁴ |
| Outside-count sliding | O(n) | O(1) | Canonical |
When to use which
- Balance target on fixed alphabet → outside counts.
- Any character allowed as replacement → this template.
- Fixed replacement char → different constraint.
Related problems
- Longest Repeating Character Replacement
- Minimum Window Substring
- Longest Substring with At Most K Distinct Characters