Total Appeal of A String

Problem Description

The appeal of a string is the number of distinct characters found in the string. Given a string s, return the total appeal of all of its substrings.

Key Insights

• A substring is a contiguous sequence of characters within a string.
• The appeal of a substring is defined as the number of distinct characters in it.
• Instead of generating all substrings, we can track the contribution of each character to the total appeal using its last seen position.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (only a fixed number of variables are used)

Solution

To efficiently calculate the total appeal of all substrings, we can iterate over each character in the string while maintaining a record of the last seen index of each character. For each character at index i, we can determine how many substrings end at that character and include it. The contribution of each character to the total appeal can be calculated based on its last occurrence.

We use a dictionary (or an array since we are dealing with lowercase letters) to store the last seen indices of characters. The total appeal can be computed as follows:

1. Initialize a variable for total appeal.
2. For each character in the string, calculate its contribution based on its last seen index.
3. Update the last seen index for the character.
4. Sum up the contributions to compute the total appeal.

Code Solutions