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.

828. Count Unique Characters of All Substrings of a Given String
``````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);
}
``````