Leetcode 1234: Replace the Substring for Balanced String

https://leetcode.com/contest/weekly-contest-159/problems/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'.

Notes:

This question can be solved by the sliding window method.

Since we can change the chars in the substring by any other chars, the counting of the rest chars outside the substring can always be increased or no change.

Thus, if it can be modified to be a balanced string, for each kind of char, the counting outside the substring need to be no larger than len / 4.

Then a sliding window can solve it.

See the code below:

class Solution {
public:
    int balancedString(string s) {
        int len = s.size(), res = len;
        unordered_map<char, int> mp;
        for(auto &a : s) ++mp[a];//counts ouside the windwo
        for(int i=0, j=0; j<len; ++j) {
            --mp[s[j]];//in the window
            while(i<len && mp['Q'] <= len/4 && mp['W'] <= len/4 && mp['E'] <= len/4 && mp['R'] <= len/4) {
                res = min(res, j - i + 1);
                ++mp[s[i++]];
            }
        }
        return res;
    }
};

A binary search method can also solve this problem. The min = 0, the max = length. Then the question become to find whether there is substring of length = mid = min + (max - min) / 2 existed, which can leave the remaining strings with the counts of each char no larger than len / 4.