Replace the Substring for Balanced String

MEDIUM

Description

You are given a string s of length n containing only four kinds of characters: 'Q', 'W', 'E', and 'R'.

A string is said to be balanced if each of its characters appears n / 4 times where n is the length of the string.

Return the minimum length of the substring that can be replaced with any other string of the same length to make s balanced. If s is already balanced, return 0.

Example 1:

Input: s = "QWER"
Output: 0
Explanation: s is already balanced.

Example 2:

Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3:

Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER".

Constraints:

n == s.length
4 <= n <= 10⁵
n is a multiple of 4.
s contains only 'Q', 'W', 'E', and 'R'.

Approaches

Checkout 2 different approaches to solve Replace the Substring for Balanced String. Click on different approaches to view the approach and algorithm in detail.

Brute Force Enumeration

This approach iterates through every possible substring and checks if replacing it could lead to a balanced string. A replacement is possible if the counts of characters outside the chosen substring do not exceed the target count k = n / 4. We are looking for the shortest such substring.

Algorithm

Calculate the target count k = n / 4.
Calculate the total frequency of each character ('Q', 'W', 'E', 'R') in the original string s.
If the string is already balanced (all counts equal k), return 0.
Initialize minLength to n.
Use two nested loops to iterate through all possible start (i) and end (j) indices of a substring.
For each substring s[i...j], determine the character counts within this substring (windowCount).
Check if this substring is a valid candidate for replacement. This is true if for every character c, totalCount[c] - windowCount[c] <= k. This condition ensures that the characters remaining outside the window can be part of a balanced string.
If the condition is met, update minLength = min(minLength, j - i + 1).
After checking all substrings, return minLength.

The core idea is to test every single substring as a potential candidate for replacement. For a substring s[i...j] to be a valid choice, the part of the string that remains untouched, s[0...i-1] and s[j+1...n-1], must be 'fixable'. This means that for each character, its count in the untouched parts must not be more than the n/4 limit, since we can only add characters during the replacement, not remove them from the outside. We can optimize the counting process, but the fundamental O(N^2) complexity of checking every substring remains.

class Solution {
    public int balancedString(String s) {
        int n = s.length();
        int k = n / 4;
        int[] totalCount = new int[128];
        for (char c : s.toCharArray()) {
            totalCount[c]++;
        }

        // Check if already balanced
        if (totalCount['Q'] == k && totalCount['W'] == k && totalCount['E'] == k && totalCount['R'] == k) {
            return 0;
        }

        int minLen = n;
        // Iterate over all possible substrings s[i..j]
        for (int i = 0; i < n; i++) {
            int[] windowCount = new int[128];
            for (int j = i; j < n; j++) {
                // Add current character to the window
                windowCount[s.charAt(j)]++;
                
                // Check if replacing this window can make the string balanced
                if (totalCount['Q'] - windowCount['Q'] <= k &&
                    totalCount['W'] - windowCount['W'] <= k &&
                    totalCount['E'] - windowCount['E'] <= k &&
                    totalCount['R'] - windowCount['R'] <= k) {
                    
                    minLen = Math.min(minLen, j - i + 1);
                }
            }
        }
        return minLen;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the string. The two nested loops iterate through all `O(N^2)` possible substrings. The work inside the inner loop is constant time.Space Complexity: O(1), as we only use a few arrays of constant size (e.g., 128 for ASCII characters) to store character counts.

Pros and Cons

Pros:

Conceptually straightforward and easier to implement than more optimized solutions.

Cons:

This approach is too slow for the given constraints (n up to 10^5) and will result in a Time Limit Exceeded error on most platforms.

Code Solutions

Checking out 3 solutions in different languages for Replace the Substring for Balanced String. Click on different languages to view the code.

class Solution {
public
  int balancedString(String s) {
    int[] cnt = new int[4];
    String t = "QWER";
    int n = s.length();
    for (int i = 0; i < n; ++i) {
      cnt[t.indexOf(s.charAt(i))]++;
    }
    int m = n / 4;
    if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m) {
      return 0;
    }
    int ans = n;
    for (int i = 0, j = 0; i < n; ++i) {
      cnt[t.indexOf(s.charAt(i))]--;
      while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m &&
             cnt[3] <= m) {
        ans = Math.min(ans, i - j + 1);
        cnt[t.indexOf(s.charAt(j++))]++;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Replace the Substring for Balanced String

Patterns:

Sliding Window

Data Structures:

String

Companies:

Accolite |