Solution: Total Appeal of a String

Statement

Given a string s, return its total appeal, which is calculated by summing the appeals of all its substringsA substring is a contiguous sequence of characters within a string..

The appeal of a string is defined as the count of unique characters present in that string.

For instance, the appeal of “xyzxz” is $3$, as it contains three distinct characters: ‘x’, ‘y’, and ‘z’.

Constraints:

• $1 \leq$ s.length $\leq 10^3$

• s consists of only lowercase English letters.

Solution

The key intuition for solving this problem efficiently is to focus on the contribution of each character to the total appeal, rather than processing all possible substrings. In any substring, each character contributes only once to the total appeal, regardless of how many times it appears. Therefore, we can consider only the first occurrence of each character in any substring as contributing to the total appeal. To achieve this, we keep track of the last index of each character, which helps us identify when a character appears again, allowing us to avoid counting it multiple times.

To implement this, we calculate the following two values for each character c in the string:

1. The number of substrings that end at c. This is calculated by finding the distance from the current index to the last occurrence of c.

2. The number of substrings that start from c and extend to the end of the string. This is simply the total length of the string minus the current index.

The product of these two values gives us the contribution of c to the total appeal. The first value counts the substrings containing an occurrence of c, and each of these substrings can be concatenated with the substrings formed using the rest of the characters to create new substrings.

Using the above intuition, the solution can be implemented as follows:

1. Create a hash map, track, to store the last index where each character appeared in the string. It's initialized to $-1$ for characters that haven't been seen yet. The maximum number of values that this hash map will store is $26$.

2. Create a variable, appeal, to accumulate the total appeal sum.

3. For each character c at index i in the string, calculate the contribution of c to the total appeal.

   1. Determine how many new substrings can be formed that end with the current character c. We do this using i - track[c].

      1. If track[c] is $-1$ (meaning c hasn't appeared before), then i - track[c] is simply $i + 1$ (all substrings from the start up to index i).

      2. If track[c] is a valid index, this expression gives the count of substrings that include the current position but exclude previous occurrences of c.

   2. Calculate how many substrings can start from the current index i to the end of the string, which can be calculated using n - i.

   3. The product of these two values gives the total number of substrings contributed by the current character c. Add the result of this product to appeal.

4. After calculating the contribution, update the track dictionary to record that the last occurrence of character c is now at index i.

5. After processing all characters, return the accumulated result appeal, which is the total appeal sum.

Let’s look at the following illustration to get a better understanding of the solution: