The appeal of a string is the number of distinct characters found in the string.
"abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.Given a string s, return the total appeal of all of its substrings.
A substring is a contiguous sequence of characters within a string.
Example 1:
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:
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 <= 105s consists of lowercase English letters.In #2262 Total Appeal of A String, the goal is to compute the total appeal of all substrings, where the appeal of a substring equals the number of distinct characters it contains. A brute-force approach that generates every substring and counts unique characters would be far too slow.
The key insight is to evaluate how much each character contributes to the total appeal as the string is processed from left to right. Using a hash table (or array) to track the last occurrence of every character, we can determine how many new substrings gain an additional distinct character when that character appears again.
This idea naturally leads to a dynamic programming style accumulation where we keep track of the contribution of substrings ending at the current index. By updating the contribution based on the previous position of the character, we avoid recomputing distinct counts for each substring.
This optimized method processes the string in O(n) time while maintaining constant extra space for character tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Last Occurrence Tracking | O(n) | O(1) |
Back To Back SWE
Use these hints if you're stuck. Try solving on your own first.
Consider the set of substrings that end at a certain index i. Then, consider a specific alphabetic character. How do you count the number of substrings ending at index i that contain that character?
The number of substrings that contain the alphabetic character is equivalent to 1 plus the index of the last occurrence of the character before index i + 1.
The total appeal of all substrings ending at index i is the total sum of the number of substrings that contain each alphabetic character.
To find the total appeal of all substrings, we simply sum up the total appeal for each index.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems similar to Total Appeal of A String appear in top technical interviews because they test understanding of substring contribution techniques and optimization with hash maps or dynamic programming. Interviewers often look for the ability to reduce brute force solutions to linear time.
A hash table or fixed-size array is typically used to store the last seen index of each character. Since the problem usually involves lowercase English letters, an array of size 26 works efficiently and provides constant-time updates.
The optimal approach uses a dynamic programming style contribution method combined with tracking the last occurrence of each character. Instead of evaluating every substring, it calculates how each character increases the appeal of substrings ending at the current position. This reduces the problem to a single linear pass through the string.
A brute force method would generate all substrings and compute the number of distinct characters for each. Since there are O(n^2) substrings and checking distinct characters may take additional time, this approach becomes too slow for large inputs.