# LC 1234. Replace the Substring for Balanced String

### [Problem link](https://leetcode.com/problems/replace-the-substring-for-balanced-string/)

###### tags: `leedcode` `medium` `c++` `Sliding Window`

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

A string is said to be **balanced** if each of its characters appears <code>n / 4</code> times where <code>n</code> 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 <code>s</code> **balanced** . If s is already **balanced** , return <code>0</code>.

**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:**

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

## Solution 1 - Sliding Window
#### C++

class Solution {
public:
    int balancedString(string s) {
        unordered_map<char, int> freq;
        for (char& c: s) {
            freq[c]++;
        }
        int m = s.size() / 4;
        if (freq['Q'] == m && freq['W'] == m && freq['E'] == m && freq['R'] == m) {
            return 0;
        }

        int ans = s.size();
        int l = 0;
        for (int r = 0; r < s.size(); r++) {
            freq[s[r]]--;
            while (freq['Q'] <= m && freq['W'] <= m && freq['E'] <= m && freq['R'] <= m) {
                ans = min(ans, r - l + 1);
                freq[s[l]]++;
                l++;
            }
        }
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
[0x3F](https://leetcode.cn/problems/replace-the-substring-for-balanced-string/solutions/2108358/tong-xiang-shuang-zhi-zhen-hua-dong-chua-z7tu/)