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.Problem Overview: The appeal of a string is the number of distinct characters it contains. For a given string s, the task is to compute the sum of appeal values for every possible substring. A direct enumeration quickly becomes expensive because a string of length n has O(n^2) substrings.
Approach 1: Brute Force Substring Enumeration (O(n^2) time, O(1) space)
Generate every substring and track how many distinct characters it contains. Fix a starting index i, extend the substring to the right, and maintain a small frequency array or set to count unique characters as you iterate. Each extension updates the distinct count and adds it to the total appeal. This reduces the naive O(n^3) approach (recomputing uniqueness each time) down to O(n^2) by reusing the character counts while expanding the window.
This method is easy to reason about and useful for validating logic on small inputs. However, with n up to 105, quadratic growth becomes impractical.
Approach 2: Optimized Contribution with Last Occurrence Tracking (O(n) time, O(1) space)
The optimal insight: instead of counting distinct characters for every substring, compute how much each character contributes to the total appeal. When you process index i, determine how many substrings ending at i gain a new distinct character because of s[i]. If the previous occurrence of this character was at index last, then it contributes to i - last new substrings.
Maintain an array storing the last seen position for each character. As you iterate through the string, calculate the contribution of the current character and add it to a running total. A dynamic programming style variable can also track the total appeal of substrings ending at the current index, which accumulates into the final answer. Each step performs constant work, producing an O(n) solution.
This pattern appears often in string contribution problems and is closely related to techniques used in dynamic programming and frequency tracking with a hash table. The key idea is shifting perspective from substrings to per‑character impact.
Recommended for interviews: Interviewers expect the contribution-based solution with last occurrence tracking. Demonstrating the brute force approach first shows you understand the definition of substring appeal, but reaching the O(n) contribution insight proves strong algorithmic thinking and familiarity with substring contribution techniques.
This approach utilizes the idea of tracking the last occurrence of each character to efficiently calculate the total appeal of all substrings. We maintain a map to record the last index at which each character was seen. For each character in the string, we calculate how many substrings end with that character and contribute the count of distinct characters to the total appeal. If a character is seen at index i, and its last occurrence was at index j, then all substrings with this character from j+1 to i need to be recalculated for distinct characters.
This C code defines a function totalAppealOfString which calculates the total appeal of all substrings. It uses an array lastPos of size 26 to track the last occurrence of each character. The currentAppeal accumulates the appeal of substrings ending at the current index by adding the count of new substrings that include the current character since its last occurrence. The total appeal is the sum of all computed currentAppeal.
Time Complexity: O(n), where n is the length of the string, since we only need a single pass through the string.
Space Complexity: O(1), using a fixed-size array for character counts.
We can enumerate all the substrings that end with each character s[i] and calculate their gravitational value sum t. Finally, we add up all the t to get the total gravitational value sum.
When we reach s[i], which is added to the end of the substring that ends with s[i-1], we consider the change of the gravitational value sum t:
If s[i] has not appeared before, then the gravitational value of all substrings that end with s[i-1] will increase by 1, and there are a total of i such substrings. Therefore, t increases by i, plus the gravitational value of s[i] itself, which is 1. Therefore, t increases by a total of i+1.
If s[i] has appeared before, let the last appearance position be j. Then we add s[i] to the end of the substrings s[0..i-1], [1..i-1], s[2..i-1], cdots, s[j..i-1]. The gravitational value of these substrings will not change because s[i] has already appeared in these substrings. The gravitational value of the substrings s[j+1..i-1], s[j+2..i-1], cdots, s[i-1] will increase by 1, and there are a total of i-j-1 such substrings. Therefore, t increases by i-j-1, plus the gravitational value of s[i] itself, which is 1. Therefore, t increases by a total of i-j.
Therefore, we can use an array pos to record the last appearance position of each character. Initially, all positions are set to -1.
Next, we traverse the string, and each time we update the gravitational value sum t of the substring that ends with the current character to t = t + i - pos[c], where c is the current character. We add t to the answer. Then we update pos[c] to the current position i. We continue to traverse until the end of the string.
The time complexity is O(n), and the space complexity is O(|\Sigma|), where n is the length of the string s, and |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Optimized Approach using Last Occurrence Tracking | Time Complexity: O(n), where n is the length of the string, since we only need a single pass through the string. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n^2) | O(1) | Useful for understanding the problem or verifying correctness on small inputs |
| Last Occurrence Contribution Tracking | O(n) | O(1) | Optimal solution for large strings; commonly expected in coding interviews |
Contribution Technique | Leetcode Weekly Episode 7 | Leetcode 2262 | Vivek Gupta • Vivek Gupta • 9,227 views views
Watch 9 more video solutions →Practice Total Appeal of A String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor