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.
| 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