2262. Total Appeal of A String Hard

1/**
2 * [2262] Total Appeal of A String
3 *
4 * The appeal of a string is the number of distinct characters found in the string.
5 * 
6 * For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.
7 * 
8 * Given a string s, return the total appeal of all of its substrings.
9 * A substring is a contiguous sequence of characters within a string.
10 *  
11 * Example 1:
12 * 
13 * Input: s = "abbca"
14 * Output: 28
15 * Explanation: The following are the substrings of "abbca":
16 * - Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
17 * - Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
18 * - Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
19 * - Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
20 * - Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.
21 * The total sum is 5 + 7 + 7 + 6 + 3 = 28.
22 * 
23 * Example 2:
24 * 
25 * Input: s = "code"
26 * Output: 20
27 * Explanation: The following are the substrings of "code":
28 * - Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
29 * - Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
30 * - Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
31 * - Substrings of length 4: "code" has an appeal of 4. The sum is 4.
32 * The total sum is 4 + 6 + 6 + 4 = 20.
33 * 
34 *  
35 * Constraints:
36 * 
37 * 1 <= s.length <= 10^5
38 * s consists of lowercase English letters.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/total-appeal-of-a-string/
44// discuss: https://leetcode.com/problems/total-appeal-of-a-string/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn appeal_sum(s: String) -> i64 {
50        let mut ans: i64 = 0;
51        let len = s.len();
52        let chs: Vec<char> = s.chars().collect();
53        let mut last_appear: Vec<i64> = vec![-1; 26];
54        for i in 0..len {
55            let left = i as i64 - last_appear[chs[i] as usize - 'a' as usize];
56            let right = (len - i) as i64;
57            ans += left * right;
58
59            last_appear[chs[i] as usize - 'a' as usize] = i as i64;
60        }
61        ans
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_2262_1() {
73        assert_eq!(Solution::appeal_sum(String::from("code")), 20);
74        assert_eq!(Solution::appeal_sum(String::from("abbca")), 28);
75    }
76}
77