##### Welcome to Subscribe On Youtube

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

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

############

class Solution {
public int balancedString(String s) {
int[] cnt = new int[4];
String t = "QWER";
int n = s.length();
for (int i = 0; i < n; ++i) {
cnt[t.indexOf(s.charAt(i))]++;
}
int m = n / 4;
if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m) {
return 0;
}
int ans = n;
for (int i = 0, j = 0; i < n; ++i) {
cnt[t.indexOf(s.charAt(i))]--;
while (j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m) {
ans = Math.min(ans, i - j + 1);
cnt[t.indexOf(s.charAt(j++))]++;
}
}
return ans;
}
}

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

• class Solution:
def balancedString(self, s: str) -> int:
cnt = Counter(s)
n = len(s)
if all(v <= n // 4 for v in cnt.values()):
return 0
ans, j = n, 0
for i, c in enumerate(s):
cnt[c] -= 1
while j <= i and all(v <= n // 4 for v in cnt.values()):
ans = min(ans, i - j + 1)
cnt[s[j]] += 1
j += 1
return ans

############

# 1234. Replace the Substring for Balanced String
# https://leetcode.com/problems/replace-the-substring-for-balanced-string/

class Solution:
def balancedString(self, s: str):
n = len(s)
desired = n // 4
c = Counter(s)

for key in c:
if c[key] > 0:
c[key] = max(0, c[key] - desired)

res = n
i = 0

for j,x in enumerate(s):
c[x] -= 1

while i < n and all(val <= 0 for val in c.values()):
res = min(res, j - i + 1)
c[s[i]] += 1
i += 1

return res

def balancedString(self, s: str):
n = len(s)
c = Counter(s)
res = float('inf')
i = 0

for j,x in enumerate(s):
c[x] -= 1

while i < n and all(val <= n//4 for val in c.values()):
res = min(res, j - i + 1)
c[s[i]] += 1
i += 1

return res

• func balancedString(s string) int {
cnt := [4]int{}
t := "QWER"
n := len(s)
for i := range s {
cnt[strings.IndexByte(t, s[i])]++
}
m := n / 4
if cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m {
return 0
}
ans := n
for i, j := 0, 0; i < n; i++ {
cnt[strings.IndexByte(t, s[i])]--
for j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m {
ans = min(ans, i-j+1)
cnt[strings.IndexByte(t, s[j])]++
j++
}
}
return ans
}

func min(a, b int) int {
if a < b {
return a
}
return b
}