#2262

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Total Appeal of A String

Calculate the total appeal of all substrings by counting distinct characters efficiently using state transition DP and hash tracking.

hash table string dynamic programming

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.

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.

terminal

Solution

Solution 1: Enumeration

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.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def appealSum(self, s: str) -> int:
        ans = t = 0
        pos = [-1] * 26
        for i, c in enumerate(s):
            c = ord(c) - ord('a')
            t += i - pos[c]
            ans += t
            pos[c] = i
        return ans

Continue Practicing

#2266 count number of texts #2370 longest ideal subsequence #2606 find the substring with maximum cost