This problem can be solved by using a state transition dynamic programming approach that keeps track of the last seen position of each character. For each index, compute the contribution of substrings ending at that index to the total appeal. Using a hash table to store character positions avoids recalculating distinct counts repeatedly, giving a linear time solution with careful implementation.
Problem Statement
You are given a string s consisting of lowercase English letters. The appeal of a string is defined as the number of distinct characters in it. Your task is to return the sum of appeals of all possible substrings of s.
A substring is any contiguous sequence of characters within the string s. Efficiently computing this total appeal requires considering how each character contributes to substrings ending at its position and combining these contributions across the entire string.
Examples
Example 1
Input: s = "abbca"
Output: 28
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
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 <= 105
- s consists of lowercase English letters.
Solution Approach
Track last seen positions
Use a hash table to store the last index each character appeared. For each character at index i, calculate how many substrings end at i that include this character and add that to the running total appeal.
Apply state transition DP
Maintain a DP array where dp[i] represents the total appeal of substrings ending at index i. Use the formula dp[i] = dp[i-1] + (i - last_seen[char]) to compute efficiently, reflecting the incremental contribution of the current character.
Aggregate results
Sum all dp[i] values across the string to get the total appeal of all substrings. This approach ensures each substring's distinct character contribution is counted exactly once while avoiding nested loops over substrings.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) since each character is processed once and hash table lookups are constant. Space complexity is O(1) with a fixed-size table for 26 lowercase letters, or O(n) if storing DP values explicitly.
What Interviewers Usually Probe
- Ask how to avoid recalculating distinct counts for overlapping substrings.
- Probe understanding of state transition DP and its application to substring contributions.
- Check if candidate can optimize using a hash table to track last seen positions.
Common Pitfalls or Variants
Common pitfalls
- Counting distinct characters by scanning every substring leads to O(n^2) time, which is too slow.
- Forgetting to update last seen positions after processing each character causes incorrect contributions.
- Confusing total appeal of substrings ending at i with substrings starting at i, resulting in double-counting or omissions.
Follow-up variants
- Compute the total appeal only for substrings of fixed length k.
- Find the substring with maximum appeal instead of total appeal.
- Apply the same approach for strings with uppercase and lowercase letters.
How GhostInterview Helps
- Automatically tracks state transitions and last seen positions to prevent calculation errors.
- Highlights the incremental contribution of each character to substrings, guiding correct DP formulation.
- Visualizes the mapping from indices to substring appeal sums to ensure accurate aggregation.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the total appeal of a string in this problem?
It is the sum of distinct character counts across all substrings of the given string s.
Why use state transition DP for this problem?
Because it efficiently computes each substring's contribution to the total appeal without scanning every substring individually.
How does tracking last seen positions help?
It allows calculating how many substrings end at a given index include a specific character, avoiding repeated distinct count computations.
Can this approach handle large strings efficiently?
Yes, using hash tables and state transition DP ensures O(n) time and minimal extra space, suitable for strings up to length 10^5.
Are there common mistakes to watch for?
Yes, forgetting to update last seen positions, using nested loops over substrings, or miscalculating contributions at each index can all produce wrong totals.
Need direct help with Total Appeal of A String instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Total Appeal of A String from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Calculate the total number of possible original texts from a pressed key sequence using state transition dynamic programming efficiently.
Open problem page#2370 Longest Ideal SubsequenceThe Longest Ideal Subsequence problem involves finding the longest subsequence where each character has a difference of at most k in alphabetical order.
Open problem page#2606 Find the Substring With Maximum CostFind the Substring With Maximum Cost requires calculating substring values using a hash lookup for character costs, with dynamic scanning optimization.
Open problem page