1358. Number of Substrings Containing All Three Characters

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

 

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters ab and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again). 

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters ab and c are "aaacb", "aacb" and "acb". 

Example 3:

Input: s = "abc"
Output: 1

 

Constraints:

  • 3 <= s.length <= 5 x 10^4
  • s only consists of a, b or characters.

Rust Solution

struct Solution;

impl Solution {
    fn number_of_substrings(s: String) -> i32 {
        let mut count: [usize; 3] = [0; 3];
        let s: Vec<u8> = s.bytes().collect();
        let n = s.len();
        let mut j = 0;
        let mut res = 0;
        for i in 0..n {
            count[(s[i] - b'a') as usize] += 1;
            while count[0] > 0 && count[1] > 0 && count[2] > 0 {
                count[(s[j] - b'a') as usize] -= 1;
                j += 1;
            }
            res += j;
        }
        res as i32
    }
}

#[test]
fn test() {
    let s = "abcabc".to_string();
    let res = 10;
    assert_eq!(Solution::number_of_substrings(s), res);
    let s = "aaacb".to_string();
    let res = 3;
    assert_eq!(Solution::number_of_substrings(s), res);
    let s = "abc".to_string();
    let res = 1;
    assert_eq!(Solution::number_of_substrings(s), res);
}

Having problems with this solution? Click here to submit an issue on github.