# Replace the Substring for Balanced String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/replace-the-substring-for-balanced-string)
Canonical: https://scaleengineer.com/dsa/problems/replace-the-substring-for-balanced-string
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
**Companies:** [Accolite](https://scaleengineer.com/companies/accolite)
---
## Problem
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 <= 105`
* `n` is a multiple of `4`.
* `s` contains only `'Q'`, `'W'`, `'E'`, and `'R'`.

# Approaches
## 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.
**Time:** 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:** O(1), as we only use a few arrays of constant size (e.g., 128 for ASCII characters) to store character counts.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Sliding Window on Excess Characters
A more efficient approach rephrases the problem. Instead of checking what's *outside* a substring, we determine what needs to be *inside* it. For the string to become balanced, we must replace a substring that contains all the 'excess' characters. An excess character is one whose total count is greater than `n/4`. The problem then becomes finding the shortest substring that contains at least the required number of each excess character. This is a classic sliding window problem.
**Time:** O(N), where N is the length of the string. The `right` pointer traverses the string once from left to right, and the `left` pointer does the same. Each character is processed a constant number of times. · **Space:** O(1), as the frequency maps/arrays used for counts have a constant size (for 4 characters, or 128 for all ASCII).
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; Optimal space complexity.
**Cons:** The logic of transforming the problem and applying the sliding window can be less intuitive to come up with compared to the brute-force method.
### Explanation
This optimal solution hinges on a key insight: the characters we can change are within the replacement substring. The characters outside are fixed. Therefore, the counts of characters outside the substring must be at most `k = n/4`. This is equivalent to saying that the substring we replace must contain enough of each character to reduce its total count down to `k`. For example, if there are 7 'Q's and `k=5`, we have an excess of 2 'Q's. The substring we replace must contain at least 2 'Q's. We can find the minimum length of such a substring using the sliding window technique.

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

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

        // Determine excess characters that need to be in the window
        int[] excess = new int[128];
        boolean needsReplacement = false;
        for (char c : "QWER".toCharArray()) {
            if (count[c] > k) {
                excess[c] = count[c] - k;
                needsReplacement = true;
            }
        }

        if (!needsReplacement) return 0; // Should be caught by first check, but for clarity

        int left = 0;
        int minLen = n;
        int[] windowCount = new int[128];

        for (int right = 0; right < n; right++) {
            // Expand window
            windowCount[s.charAt(right)]++;

            // Shrink window while it's valid
            while (windowCount['Q'] >= excess['Q'] &&
                   windowCount['W'] >= excess['W'] &&
                   windowCount['E'] >= excess['E'] &&
                   windowCount['R'] >= excess['R']) {
                
                minLen = Math.min(minLen, right - left + 1);
                
                // Shrink from the left
                windowCount[s.charAt(left)]--;
                left++;
            }
        }
        return minLen;
    }
}
```
### Algorithm
*   Calculate the target count `k = n / 4`.
*   Calculate the total frequency of each character in `s`.
*   Determine the number of excess characters for each type. For a character `c`, `excess[c] = max(0, totalCount[c] - k)`.
*   If all `excess` counts are 0, the string is already balanced, so return 0.
*   Initialize two pointers, `left = 0` and `right = 0`, to define a window. Also, initialize `minLength = n` and a `windowCount` map/array.
*   Iterate `right` from `0` to `n-1` to expand the window to the right.
*   At each step, add `s[right]` to the window and update `windowCount`.
*   Check if the current window is 'valid' by comparing `windowCount` with `excess`. The window is valid if `windowCount[c] >= excess[c]` for all characters `c`.
*   If the window is valid, it's a potential solution. Update `minLength = min(minLength, right - left + 1)`. Then, try to find a smaller valid window by shrinking it from the left: decrement the count of `s[left]` and increment `left`. Repeat this as long as the window remains valid.
*   Continue expanding with `right` until the end of the string.
*   Return `minLength`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int balancedString(string s) {
    int cnt[4]{};
    string t = "QWER";
    int n = s.size();
    for (char &c : s) {
      cnt[t.find(c)]++;
    }
    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.find(s[i])]--;
      while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m &&
             cnt[3] <= m) {
        ans = min(ans, i - j + 1);
        cnt[t.find(s[j++])]++;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def balancedString(self, s: str) -> int: cnt = Counter(s) n = len(s) if all(v <= n // 4 for v in cnt . values()): return 0 ans, j = n, 0 for i, c in enumerate(s): cnt[c] -= 1 while j <= i and all(v <= n // 4 for v in cnt . values()): ans = min(ans, i - j + 1) cnt[s[j]] += 1 j += 1 return ans

```