Course4all

Replace the Substring for Balanced String

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Sliding Window.

Replace the Substring for Balanced String

Find the minimum length of a substring that can be replaced to make all characters ('Q', 'W', 'E', 'R') appear exactly n/4 times.

Visual Representation

s = "QQWE", n = 4, target = 1 Counts: Q:2, W:1, E:1, R:0 Over-limit: Q (2 > 1) Goal: Find smallest window that contains the 'excess' characters. Window [Q] (at index 0): Remaining Counts outside window: Q:1, W:1, E:1, R:0 All remaining counts <= target? YES! (1, 1, 1, 0 <= 1) Min Length = 1
Medium

Examples

Input: s = "QQWE"
Output: 1
Approach 1

Level I: Brute Force

Intuition

Iterate through every possible substring that could be replaced. For each substring, calculate the character frequencies of the remaining part of the string. If all counts (Q, W, E, R) in the remaining part are ≤n/4\le n/4, then the substring can be replaced to make the string balanced. Find the minimum length of such a substring.

Thought Process

  1. Outer loop i from 0 to n-1.
  2. Inner loop j from i to n-1.
  3. Count characters in s[0...i-1] and s[j+1...n-1].
  4. If all counts ≤n/4\le n/4, minLen = min(minLen, j - i + 1).
  5. Handle the special case where the string is already balanced (length 0).
⏱ O(N^3) (can be O(N^2) if count updated incrementally)💾 O(1)

Detailed Dry Run

Substring [i, j]Remaining CountsValid?
GlobalQ:2, W:1, E:1, R:0NO
[0, 0] (Q)Q:1, W:1, E:1, R:0YES! (Len 1)
[1, 1] (Q)Q:1, W:1, E:1, R:0YES! (Len 1)
java
public class Main {
    public static int balancedString(String s) {
        int n = s.length(), m = n / 4;
        int[] total = new int[128];
        for (char c : s.toCharArray()) total[c]++;
        if (total['Q'] <= m && total['W'] <= m && total['E'] <= m && total['R'] <= m) return 0;

        int minLen = n;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int[] count = new int[128];
                for (int k = 0; k < i; k++) count[s.charAt(k)]++;
                for (int k = j + 1; k < n; k++) count[s.charAt(k)]++;
                if (count['Q'] <= m && count['W'] <= m && count['E'] <= m && count['R'] <= m) {
                    minLen = Math.min(minLen, j - i + 1);
                }
            }
        }
        return minLen;
    }

    public static void main(String[] args) {
        System.out.println(balancedString("QQWE")); // 1
    }
}
Approach 2

Level II: Binary Search on Window Size (O(N log N))

Intuition

We can binary search for the minimum length L of the substring to replace. For a fixed length L, we check if any substring of size L can be replaced to make the entire string balanced. A string is balanced if all counts of 'Q', 'W', 'E', 'R' are exactly n/4n/4. Replacing a substring means the counts of remaining characters must be ≤n/4\le n/4.

Thought Process

  1. Target count for each character is n/4.
  2. In binary search, for a fixed mid length:
    • Slide a window of size mid across the string.
    • Count character frequencies outside the window.
    • If all counts outside ≤n/4\le n/4, then length mid is possible.
  3. Adjust the search range for the minimum possible mid.

Pattern: Search on Answer Space

⏱ O(N log N)💾 O(1) - alphabet size (4)
java
public class Solution {
    public int balancedString(String s) {
        int n = s.length(), target = n / 4;
        int low = 0, high = n, ans = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(s, target, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean check(String s, int target, int len) {
        int[] count = new int[256];
        for (char c : s.toCharArray()) count[c]++;
        
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]--;
            if (i >= len) count[s.charAt(i - len)]++;
            
            if (i >= len - 1) {
                if (count['Q'] <= target && count['W'] <= target && 
                    count['E'] <= target && count['R'] <= target) return true;
            }
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

A string is balanced if all counts are ≤n/4\le n/4. To make a string balanced by replacing a substring, the characters outside that substring must all have counts ≤n/4\le n/4. We search for the smallest window such that all characters remaining outside it satisfy this condition.

Patterns

  1. Window Complement: Check characters NOT in the window.
  2. Smallest Valid Window: Shrink from left while condition is met.
⏱ O(N)💾 O(1)

Detailed Dry Run

WindowCount QCount WCount ECount RValid?
Global2110NO
[Q]1110YES
[QQ]0110YES
java
public class Main {
    public static int balancedString(String s) {
        int[] count = new int[128];
        int n = s.length(), res = n, i = 0, k = n / 4;
        for (int j = 0; j < n; j++) count[s.charAt(j)]++;
        if (count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) return 0;
        for (int j = 0; j < n; j++) {
            count[s.charAt(j)]--;
            while (i < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
                res = Math.min(res, j - i + 1);
                count[s.charAt(i++)]++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(balancedString("QQWE"));
    }
}

⚠️ Common Pitfalls & Tips

The goal is finding the smallest window that contains ALL excesses. If the string is already balanced, the answer is 0.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionLongest Turbulent Subarray
Next Question →Get Equal Substrings Within Budget