Problem

The appeal of a string is the number of distinct characters found in the string.

  • For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.

Given a string s, return thetotal appeal of all of itssubstrings**.**

A substring is a contiguous sequence of characters within a string.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: s = "abbca"
Output: 28
Explanation: The following are the substrings of "abbca":
- Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.

Example 2

1
2
3
4
5
6
7
8

Input: s = "code"
Output: 20
Explanation: The following are the substrings of "code":
- Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4: "code" has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.

Solution

Method 1 – Last Occurrence Contribution (DP)

Intuition

For each character, count how many substrings end at each position where it is the rightmost occurrence, and sum their contributions.

Approach

Track the last seen index for each character. For each position, the number of substrings where s[i] is the rightmost occurrence is (i - last[c]), and each such substring contributes to the total appeal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    long long appealSum(string s) {
        vector<int> last(26, -1);
        long long res = 0, cur = 0;
        for (int i = 0; i < s.size(); ++i) {
            cur += i - last[s[i] - 'a'];
            last[s[i] - 'a'] = i;
            res += cur;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public long appealSum(String s) {
        int[] last = new int[26];
        for (int i = 0; i < 26; ++i) last[i] = -1;
        long res = 0, cur = 0;
        for (int i = 0; i < s.length(); ++i) {
            cur += i - last[s.charAt(i) - 'a'];
            last[s.charAt(i) - 'a'] = i;
            res += cur;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def appealSum(self, s: str) -> int:
        last = [-1] * 26
        res = cur = 0
        for i, c in enumerate(s):
            cur += i - last[ord(c) - ord('a')]
            last[ord(c) - ord('a')] = i
            res += cur
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn appeal_sum(s: String) -> i64 {
        let mut last = [-1; 26];
        let mut res = 0i64;
        let mut cur = 0i64;
        for (i, b) in s.bytes().enumerate() {
            let idx = (b - b'a') as usize;
            cur += (i as i64 - last[idx]);
            last[idx] = i as i64;
            res += cur;
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function appealSum(s: string): number {
    const last = Array(26).fill(-1);
    let res = 0, cur = 0;
    for (let i = 0; i < s.length; ++i) {
        const idx = s.charCodeAt(i) - 97;
        cur += i - last[idx];
        last[idx] = i;
        res += cur;
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)