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 of 4
  • 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.