1234. Replace the Substring for Balanced String

You are given a string containing only 4 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 the original string s balanced.

Return 0 if the string is already balanced.

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". 

Example 4:

Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".

Constraints:

• 1 <= s.length <= 10^5

• s.length is a multiple of 4

• s contains only 'Q', 'W', 'E' and 'R'.

// Sliding Window
int balancedString(string s) { // time: O(n); space: O(1)
    vector<int> cnt(128);
    int n = s.length(), res = n, i = 0, k = n / 4;
    for (char ch : s) ++cnt[ch];
    for (int j = 0; j < n; ++j) {
        // Add the current char into the sliding window
        --cnt[s[j]];
        while (i < n && cnt['Q'] <= k && cnt['W'] <= k && cnt['E'] <= k && cnt['R'] <= k) {
            res = min(res, j - i + 1);
            // Remove the char pointed by i from the sliding window
            ++cnt[s[i++]];
        }
    }
    return res;
}