1234. 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 of4
s
contains only'Q'
,'W'
,'E'
and'R'
.
Rust Solution
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);
}
Having problems with this solution? Click here to submit an issue on github.