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.

#2262

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

字符串的总引力

字符串的引力定义为：字符串中不同字符的数量。例如， "abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a' 、 'b' 和 'c' 。给你一个字符串 s ，返回其所有子字符串的总引力。子字符串定义为：字符串中的一个连续字符序列。示例 1：输入： s = "abbc…

哈希表字符串动态规划

题目描述

字符串的引力定义为：字符串中不同字符的数量。

例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。

给你一个字符串 s ，返回 其所有子字符串的总引力 。

子字符串 定义为：字符串中的一个连续字符序列。

示例 1：

输入：s = "abbca"
输出：28
解释："abbca" 的子字符串有：
- 长度为 1 的子字符串："a"、"b"、"b"、"c"、"a" 的引力分别为 1、1、1、1、1，总和为 5 。
- 长度为 2 的子字符串："ab"、"bb"、"bc"、"ca" 的引力分别为 2、1、2、2 ，总和为 7 。
- 长度为 3 的子字符串："abb"、"bbc"、"bca" 的引力分别为 2、2、3 ，总和为 7 。
- 长度为 4 的子字符串："abbc"、"bbca" 的引力分别为 3、3 ，总和为 6 。
- 长度为 5 的子字符串："abbca" 的引力为 3 ，总和为 3 。
引力总和为 5 + 7 + 7 + 6 + 3 = 28 。

示例 2：

输入：s = "code"
输出：20
解释："code" 的子字符串有：
- 长度为 1 的子字符串："c"、"o"、"d"、"e" 的引力分别为 1、1、1、1 ，总和为 4 。
- 长度为 2 的子字符串："co"、"od"、"de" 的引力分别为 2、2、2 ，总和为 6 。
- 长度为 3 的子字符串："cod"、"ode" 的引力分别为 3、3 ，总和为 6 。
- 长度为 4 的子字符串："code" 的引力为 4 ，总和为 4 。
引力总和为 4 + 6 + 6 + 4 = 20 。

提示：

1 <= s.length <= 10⁵
s 由小写英文字母组成

lightbulb

解题思路

方法一：枚举

我们可以枚举以每个字符 $s[i]$ 结尾的字符串，计算其引力值之和 $t$ ，最后将所有 $t$ 相加即可。

考虑遍历到 $s[i]$ 时，即把 $s[i]$ 添加到以 $s[i-1]$ 结尾的子字符串的后面，其引力值之和 $t$ 的变化情况：

如果 $s[i]$ 在之前没出现过，那么所有以 $s[i-1]$ 结尾的子字符串的引力值都会增加 $1$ ，共有 $i$ 个，所以 $t$ 增加 $i$ ，再加上 $s[i]$ 自身的引力值 $1$ ，所以 $t$ 一共增加 $i+1$ ；
如果 $s[i]$ 在之前出现过，不妨记上次出现的的位置为 $j$ ，那么我们向子字符串 $s[0..i-1]$ , $[1..i-1]$ , $s[2..i-1]$ , $\cdots$ , $s[j..i-1]$ 后面添加 $s[i]$ ，这些子字符串的引力值不会发生变化，因为 $s[i]$ 已经在这些子字符串中出现过了；而子字符串 $s[j+1..i-1]$ , $s[j+2..i-1]$ , $\cdots$ , $s[i-1]$ 的引力值都会增加 $1$ ，共有 $i-j-1$ 个，所以 $t$ 增加 $i-j-1$ ，再加上 $s[i]$ 自身的引力值 $1$ ，所以 $t$ 一共增加 $i-j$ 。

综上，我们可以用一个数组 $pos$ 记录每个字符上次出现的位置，初始时所有位置都为 $-1$ ，

接下来，我们遍历字符串，每一次我们更新以当前字符结尾的子字符串的引力值之和 $t = t + i - pos[c]$ ，其中 $c$ 是当前字符，累加 $t$ 到答案中。然后我们更新 $pos[c]$ 为当前位置 $i$ 。继续遍历直到字符串结束。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask how to avoid recalculating distinct counts for overlapping substrings.
question_mark
Probe understanding of state transition DP and its application to substring contributions.
question_mark
Check if candidate can optimize using a hash table to track last seen positions.

warning

常见陷阱

外企场景

error
Counting distinct characters by scanning every substring leads to O(n^2) time, which is too slow.
error
Forgetting to update last seen positions after processing each character causes incorrect contributions.
error
Confusing total appeal of substrings ending at i with substrings starting at i, resulting in double-counting or omissions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the total appeal only for substrings of fixed length k.
arrow_right_alt
Find the substring with maximum appeal instead of total appeal.
arrow_right_alt
Apply the same approach for strings with uppercase and lowercase letters.

help

常见问题

外企场景

继续练习

#2266 统计打字方案数 #2370 最长理想子序列 #2606 找到最大开销的子字符串