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^5s.lengthis a multiple of4scontains 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[4];
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[4];
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;
}
}