Replace the Substring for Balanced String

Master this topic with zero to advance depth.

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 $\le n/4$ , then the substring can be replaced to make the string balanced. Find the minimum length of such a substring.

Thought Process

Outer loop i from 0 to n-1.
Inner loop j from i to n-1.
Count characters in s[0...i-1] and s[j+1...n-1].
If all counts $\le n/4$ , minLen = min(minLen, j - i + 1).
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 Counts	Valid?
Global	Q:2, W:1, E:1, R:0	NO
[0, 0] (Q)	Q:1, W:1, E:1, R:0	YES! (Len 1)
[1, 1] (Q)	Q:1, W:1, E:1, R:0	YES! (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/4$ . Replacing a substring means the counts of remaining characters must be $\le n/4$ .

Thought Process

Target count for each character is n/4.
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 $\le n/4$ , then length mid is possible.
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 $\le n/4$ . To make a string balanced by replacing a substring, the characters outside that substring must all have counts $\le n/4$ . We search for the smallest window such that all characters remaining outside it satisfy this condition.

Patterns

Window Complement: Check characters NOT in the window.
Smallest Valid Window: Shrink from left while condition is met.

⏱ O(N)💾 O(1)

Detailed Dry Run

Window	Count Q	Count W	Count E	Valid?
Global	2	1	1	NO
[Q]	1	1	1	YES
[QQ]	0	1	1	YES

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.

← Previous QuestionLongest Turbulent Subarray

Next Question →Get Equal Substrings Within Budget

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.