1234

1234. Replace the Substring for Balanced String (Medium)

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

Related Topics:
Two Pointers, String

Solution 1. Sliding Window

Count the frequency of each characters. Those characters with frequency greater than N / 4 must be replaced. Find the minimum window which covers those characters that should be replaced.

// OJ: https://leetcode.com/problems/replace-the-substring-for-balanced-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int balancedString(string s) {
        int N = s.size(), ans = N, i = 0, j = 0, replace = 0;
        unordered_map<char, int> m;
        for (char c : s) m[c]++;
        for (auto &[c, cnt] : m) {
            if ((m[c] = max(0, cnt - N / 4)) > 0) ++replace;
        }
        if (replace == 0) return 0;
        while (j < N) {
            replace -= --m[s[j++]] == 0;
            while (replace <= 0) {
                ans = min(ans, j - i);
                replace += m[s[i++]]++ == 0;
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/replace-the-substring-for-balanced-string/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/JavaC%2B%2BPython-Sliding-Window
class Solution {
public:
    int balancedString(string s) {
        unordered_map<char, int> m;
        int N = s.size(), ans = N, i = 0, k = N / 4;
        for (char c : s) ++m[c];
        for (int j = 0; j < N; ++j) {
            --m[s[j]];
            while (i < N && m['Q'] <= k && m['W'] <= k && m['E'] <= k && m['R'] <= k) {
                ans = min(ans, j - i + 1);
                ++m[s[i++]];
            }
        }
        return ans;
    }
};