828. Count Unique Characters of All Substrings of a Given String

Let's define a function countUniqueChars(s) that returns the number of unique characters on s, for example if s = "LEETCODE" then "L", "T","C","O","D" are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

On this problem given a string s we need to return the sum of countUniqueChars(t) where t is a substring of s. Notice that some substrings can be repeated so on this case you have to count the repeated ones too.

Since the answer can be very large, return the answer modulo 10 ^ 9 + 7.

 

Example 1:

Input: s = "ABC"
Output: 10
Explanation: All possible substrings are: "A","B","C","AB","BC" and "ABC".
Evey substring is composed with only unique letters.
Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example 2:

Input: s = "ABA"
Output: 8
Explanation: The same as example 1, except countUniqueChars("ABA") = 1.

Example 3:

Input: s = "LEETCODE"
Output: 92

 

Constraints:

  • 0 <= s.length <= 10^4
  • s contain upper-case English letters only.

Rust Solution

struct Solution;

use std::collections::HashMap;

const MOD: i64 = 1_000_000_007;

impl Solution {
    fn unique_letter_string(s: String) -> i32 {
        let n = s.len();
        let s: Vec<char> = s.chars().collect();
        let mut idx: HashMap<char, Vec<usize>> = HashMap::new();
        for i in 0..n {
            idx.entry(s[i]).or_default().push(i + 1);
        }
        let mut res = 0;
        for v in idx.values() {
            let m = v.len();
            for i in 0..m {
                let prev = if i > 0 { v[i - 1] } else { 0 };
                let next = if i + 1 < m { v[i + 1] } else { n + 1 };
                res += ((v[i] - prev) * (next - v[i])) as i64;
                res %= MOD;
            }
        }
        res as i32
    }
}

#[test]
fn test() {
    let s = "ABC".to_string();
    let res = 10;
    assert_eq!(Solution::unique_letter_string(s), res);
    let s = "ABA".to_string();
    let res = 8;
    assert_eq!(Solution::unique_letter_string(s), res);
    let s = "LEETCODE".to_string();
    let res = 92;
    assert_eq!(Solution::unique_letter_string(s), res);
}

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