Replace the Substring for Balanced String: Sliding Window Pattern

You are given a string s of length n containing only the characters 'Q', 'W', 'E', and 'R'. A string is balanced if each of the four characters appears exactly n / 4 times. Find the minimum length of a substring that you can replace so that the resulting string is balanced. If the string is already balanced, return 0.

This is LeetCode 1234: Replace the Substring for Balanced String, and it is a clean example of how the sliding window technique applies to problems that do not look like sliding window problems at first glance.

Why this problem matters

At first, this problem feels like it could require trying every possible substring and checking whether replacing it can fix the counts. That brute-force thinking leads to O(n^2) or worse. The sliding window approach brings it down to O(n), and the trick that makes it work is a subtle reframing of what the window represents.

Many sliding window problems ask you to track what is inside the window. This one flips the perspective: you track what is outside the window. That inversion is a powerful technique that shows up in other problems like Minimum Window Substring and Find All Anagrams in a String.

The key insight

You do not need to figure out what to replace the substring with. You only need to find the minimum length of a substring whose replacement could balance the string. The key observation is: if the characters outside the window all have counts at or below n / 4, then whatever characters are inside the window can be replaced to fill in whatever is missing. The window is the "replacement zone," and everything outside it must already be balanced or under the target.

So the algorithm becomes:

1. Count the frequency of every character in the full string. If all counts equal n / 4, return 0.
2. Use a sliding window. For each position of right, subtract s[right] from the outside counts (it is now inside the window).
3. While all outside counts are <= n / 4, the window is valid. Record the window length, then shrink from the left (add s[left] back to outside counts, move left forward).
4. The smallest valid window is the answer.

The solution

def balanced_string(s: str) -> int:
    n = len(s)
    target = n // 4
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1

    if all(count.get(c, 0) == target for c in "QWER"):
        return 0

    result = n
    left = 0

    for right in range(n):
        count[s[right]] -= 1

        while all(count.get(c, 0) <= target for c in "QWER"):
            result = min(result, right - left + 1)
            count[s[left]] += 1
            left += 1

    return result

Let's walk through what each piece does.

First, we count the frequency of every character in the full string. If all four characters already appear exactly n / 4 times, the string is balanced and we return 0.

The count dictionary starts with the full string's character frequencies. As the window expands (moving right forward), we decrement the count of s[right] because that character is now "inside the window" and no longer part of the outside. When we shrink (moving left forward), we increment s[left] because it is leaving the window and returning to the outside.

The validity check all(count.get(c, 0) <= target for c in "QWER") asks: "Are all characters outside the window at or below the target?" If yes, the window is large enough that we could replace its contents to balance everything. We record the window size and try shrinking to find something smaller.

Visual walkthrough

Let's trace through s = "QWQWQWER" with n = 8 and target = 2. The initial counts are Q = 3, W = 3, E = 1, R = 1. Both Q and W exceed the target, so we need a window that absorbs at least one extra Q and one extra W.

The window slides through the string, and every time we find a valid window (all outside counts at or below target), we try shrinking from the left to minimize it. The minimum valid window has length 2, which means we can replace any adjacent "QW" or "WQ" pair to balance the string.

Complexity analysis

Time is O(n). The right pointer visits each index once. The left pointer also visits each index at most once and never moves backwards. The inner validity check looks at exactly 4 characters each time, which is O(1). Total work: O(n).

Space is O(1). The count dictionary holds at most 4 keys (Q, W, E, R), regardless of the input size. No additional data structures grow with n.

The building blocks

1. Outside-the-window counting

Instead of tracking what is inside the window, you track what is outside. The window represents a "replacement zone" whose contents do not matter. You only care whether the remaining characters (outside the window) satisfy a constraint.

count = {}
for c in s:
    count[c] = count.get(c, 0) + 1

for right in range(n):
    count[s[right]] -= 1

This is the inverse of the typical sliding window state tracking. Normally you build up a window dictionary as you expand. Here, you start with the full count and subtract. The same idea applies to Minimum Window Substring, where you track how many required characters are still needed outside the window.

2. Shrink-while-valid window mechanics

The "minimum window" variant of sliding window: expand until valid, then shrink while valid to find the smallest valid window.

while all(count.get(c, 0) <= target for c in "QWER"):
    result = min(result, right - left + 1)
    count[s[left]] += 1
    left += 1

This is the same pattern used in Minimum Window Substring and Minimum Size Subarray Sum. You expand to find a valid window, then squeeze from the left to minimize it. The while loop (not if) is critical. You keep shrinking as long as the window stays valid, recording the best at each step.

Edge cases

• Already balanced: all counts equal n / 4. Return 0 immediately.
• All same character: s = "QQQQ". You need to replace 3 of them. The minimum window is 3.
• Single excess character: only one character exceeds the target. The minimum window just needs to absorb the excess of that one character.
• Multiple excess characters: the window must cover enough of each excess character, so its minimum length depends on how they are distributed across the string.
• Minimum possible length: n = 4, s = "QWER". Already balanced, return 0. Or s = "QQQQ", return 3.

From understanding to recall

You have seen how the outside-the-window trick converts a "what should I replace?" problem into a clean sliding window. The logic is compact: start with full counts, decrement on expansion, increment on contraction, and shrink while valid. But reproducing this under pressure means remembering that the counts represent the outside, not the inside, and that the validity check is <= target, not == target.

Spaced repetition is how you lock in these details. You practice writing the outside-count initialization, the expand-and-shrink loop, and the validity condition from memory at increasing intervals. After a few rounds, you see "find minimum substring to replace" and the template flows out without hesitation.

Related posts

• Minimum Window Substring - The classic hard sliding window problem that also uses the "shrink while valid" pattern with frequency counting
• Longest Substring Without Repeating Characters - The growing-window counterpart that teaches the core expand-and-shrink mechanics
• Find All Anagrams in a String - Another frequency-based sliding window problem where you track character counts inside a fixed-size window

CodeBricks breaks Replace the Substring for Balanced String into its outside-count tracking and shrink-while-valid building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sliding window problem shows up in your interview, you do not think about it. You just write it.