Replace the Substring for Balanced String — LC 1234 Minimum Window Trick

Problem Statement#

You may replace one contiguous substring of s with any string of the same length. Return the minimum length needed so each of Q, W, E, R appears exactly n / 4 times.

Constraints:

• 4 less than or equal to s.length less than or equal to 10 to the 5
• s.length is divisible by 4
• s consists only of Q, W, E, R

Input:  s = "QWER"
Output: 0

Input:  s = "QQWE"
Output: 1

Why This Problem Matters#

LeetCode 1234 — Replace the Substring for Balanced String is a Google and Amazon mid-loop favorite because it tests the "complement window" insight. The naive approach is to enumerate all substrings and check balance, which is O(n squared) and times out. The optimal trick reframes the problem: instead of asking "what substring should I replace?", ask "what is the smallest window I can leave alone that keeps the rest balanceable?"

A window is replaceable if and only if every character outside the window appears at most n / 4 times. That gives a clean monotonic predicate over right and left, which is the contract for a variable sliding window.

In real systems, this generalizes to the "minimum patch" problem: given a corrupted record, find the smallest contiguous span you must rewrite to satisfy constraints.

The Core Insight#

Let target = n / 4. Build a frequency map over the entire string. As you slide a window [left, right]:

• The characters outside the window are everything not in [left, right].
• Replace the inside with any characters you want, but you cannot change the outside.
• The window is replaceable if and only if every character outside has frequency at most target.

Maintain the global counts. When you include s[right] in the window, decrement its global count (since you are removing it from "outside"). When you advance left, increment its count (it returns to "outside").

A window is valid when every count is at most target. Track the minimum valid window length.

Visual Dry Run#

Input: s = "QQWE", target = 1.

Minimum 1.

Solution (Optimal)#

class Solution:
    def balancedString(self, s):
        n = len(s)
        target = n // 4
        count = {c: 0 for c in "QWER"}
        for c in s:
            count[c] += 1
        if all(count[c] == target for c in "QWER"):
            return 0
        left, best = 0, n
        for right, c in enumerate(s):
            count[c] -= 1
            while left < n and all(count[ch] <= target for ch in "QWER"):
                best = min(best, right - left + 1)
                count[s[left]] += 1
                left += 1
        return best

var balancedString = function(s) {
    const n = s.length;
    const target = n / 4;
    const count = { Q: 0, W: 0, E: 0, R: 0 };
    for (const c of s) count[c]++;
    if (count.Q === target && count.W === target && count.E === target && count.R === target) return 0;
    const isValid = () => count.Q <= target && count.W <= target && count.E <= target && count.R <= target;
    let left = 0, best = n;
    for (let right = 0; right < n; right++) {
        count[s[right]]--;
        while (left < n && isValid()) {
            if (right - left + 1 < best) best = right - left + 1;
            count[s[left]]++;
            left++;
        }
    }
    return best;
};

Time: O(n) — each index enters and leaves the window once. The validity check is O(4) constant. Space: O(1) — fixed 4-letter alphabet.

Common Mistakes#

• Reading the problem as "minimum substring to delete" instead of "replace with same length." The window length is what counts, not the contents.
• Comparing against target with strict less-than. The constraint is "at most" target.
• Returning 0 only when all counts equal target exactly. That is correct, but missing the early return wastes a pass.
• Not advancing left while still valid. The shrink loop is what finds the minimum length.
• Updating counts in the wrong direction — the window represents "removed" characters.

Interview Tips#

• Pitch the inversion: "I will leave a window alone and check if the outside is balanceable."
• Walk through the early-return condition for already-balanced inputs.
• Trace one example showing the shrink phase.
• Mention the constant-factor O(4) validity check; if the alphabet were large, switch to a counter that tracks "excess characters."
• Confirm divisibility of n by 4 with the interviewer.

Follow-up Questions#

• What if the alphabet has k distinct characters and n is divisible by k? Same algorithm with k-letter checks.
• What if you can replace m non-overlapping windows? Becomes a DP problem over partitions.
• Return one valid window. Track (left, right) when best updates.
• What if the cost of replacing differs by character? Optimize total cost via prefix sums.
• Streaming variant: process additional appended characters. Maintain global counts and last-known balanced state.

Key Takeaways#

• LeetCode 1234 — Replace the Substring for Balanced String solves in O(n) time and O(1) space.
• Reframe: find the smallest window to leave alone such that the outside is balanceable.
• A window is valid if every character outside appears at most n / 4 times.
• Decrement counts when entering the window, increment when leaving.
• Asked at Google and Amazon as a 30-minute string sliding window problem.
• The constant-size alphabet makes the validity check O(1).
• Same complement-window pattern appears in LC 1004 and LC 76.