Formatted question description: https://leetcode.ca/all/1234.html

# 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/

// 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/

// 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;
}
};


Java

class Solution {
public int balancedString(String s) {
Map<Character, Integer> letterIndexMap = new HashMap<Character, Integer>();
letterIndexMap.put('Q', 0);
letterIndexMap.put('W', 1);
letterIndexMap.put('E', 2);
letterIndexMap.put('R', 3);
int[] counts = new int;
int length = s.length();
int balanceLength = length / 4;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
int index = letterIndexMap.get(c);
counts[index]++;
}
boolean flag = true;
for (int i = 0; i < 4; i++) {
if (counts[i] > balanceLength) {
counts[i] -= balanceLength;
flag = false;
} else
counts[i] = 0;
}
if (flag)
return 0;
int[] actualCounts = new int;
int minLength = length;
int start = 0, end = 0;
while (end < length) {
char c = s.charAt(end);
int index = letterIndexMap.get(c);
if (counts[index] > 0) {
actualCounts[index]++;
if (canBalance(counts, actualCounts)) {
minLength = Math.min(minLength, end - start + 1);
while (start < end) {
char prevC = s.charAt(start);
start++;
int prevIndex = letterIndexMap.get(prevC);
if (counts[prevIndex] > 0) {
actualCounts[prevIndex]--;
if (actualCounts[prevIndex] < counts[prevIndex])
break;
}
minLength = Math.min(minLength, end - start + 1);
}
}
}
end++;
}
return minLength;
}

public boolean canBalance(int[] counts, int[] actualCounts) {
for (int i = 0; i < 4; i++) {
if (actualCounts[i] < counts[i])
return false;
}
return true;
}
}