leetcode 1234 - Replace the Substring for Balanced String

https://leetcode.com/problems/replace-the-substring-for-balanced-string/

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
int balancedString(string s) {
//Q W E R
int size = s.size();
unordered_map<char, int> cnt;

for (char c : s)
cnt[c]++;

string word = "QWER";
for (char c : word) {
if (cnt[c] > size /4)
cnt[c] -= size / 4;
else
cnt.erase(c);
}

if (cnt.size() == 0) return 0;

int min_len = INT_MAX;
int i = 0;

int found = 0;

for (int j = 0; j < size; j++) {
char c = s[j];

if (cnt.count(c) > 0) {
if (--cnt[c] == 0)
found++;
}

while (found == cnt.size()) {
min_len = min(min_len, j - i + 1);
c = s[i++];
if (cnt.count(c) > 0) {
if (cnt[c]++ == 0)
found--;
}
}

}

return min_len;
}
};