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.length is a multiple of 4s contains only 'Q', 'W', 'E' and 'R'.struct Solution;
impl Solution {
fn balanced_string(s: String) -> i32 {
let mut count: Vec<usize> = vec![0; 256];
let s: Vec<u8> = s.bytes().collect();
let n = s.len();
let k = n / 4;
for i in 0..n {
count[s[i] as usize] += 1;
}
let mut start = 0;
let mut end = 0;
let mut res = n;
while end < n {
count[s[end] as usize] -= 1;
end += 1;
while start < n
&& count[b'Q' as usize] <= k
&& count[b'W' as usize] <= k
&& count[b'E' as usize] <= k
&& count[b'R' as usize] <= k
{
res = res.min(end - start);
count[s[start] as usize] += 1;
start += 1;
}
}
res as i32
}
}
#[test]
fn test() {
let s = "QWER".to_string();
let res = 0;
assert_eq!(Solution::balanced_string(s), res);
let s = "QQWE".to_string();
let res = 1;
assert_eq!(Solution::balanced_string(s), res);
let s = "QQQW".to_string();
let res = 2;
assert_eq!(Solution::balanced_string(s), res);
let s = "QQQQ".to_string();
let res = 3;
assert_eq!(Solution::balanced_string(s), res);
}