Leetcode 1234: Replace the Substring for Balanced String

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^5
• n is a multiple of 4.
• s contains only 'Q', 'W', 'E', and 'R'.

Problem Analysis:

The string length is n, and balanced string make each of the 4 characters has n/4 times. And we need to find a substring, so replace it with another same length substring, it will make the whole string is balanced.

And we need to find the minimum length of such substring.

So we can think such a substring exists, and each of the 4 characters in other part of the string must be less than or equal to n/4. The lacked part we can combine to a new substring to compensate to the string to make it is balanced.

So now we can use slide window algorithm to solve it.

Solution

class Solution {
public:
    int balancedString(string s) {
        unordered_map<int, int> cnt;
        int res{(int)s.size()};
        int i{0};
        int k{(int)s.size() / 4};
        for (const auto ch: s) ++cnt[ch];
        for (int j = 0; j < s.size(); ++j) {
            --cnt[s[j]];
            while (i < s.size() && cnt['Q'] <= k && cnt['W'] <= k && cnt['E'] <= k && cnt['R'] <= k) {
                res = min(res, j - i + 1);
                cnt[s[i++]] += 1;
            }
        }

        return res;
    }
};

Time complexity is O(n)

Space complexity is O(1)