字符串的总引力

难度: Hard

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

例如，"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 由小写英文字母组成

Submission

运行时间: 100 ms

内存: 16.4 MB

#https://leetcode.cn/problems/total-appeal-of-a-string/solutions/1461618/by-endlesscheng-g405/?company_slug=bytedance
class Solution:
    def appealSum(self, s: str) -> int:
        ans, sum_g, last = 0, 0, {}
        for i,c in enumerate(s):
            sum_g += i-last.get(c,-1)
            ans += sum_g
            last[c] = i
        return ans

Explain

这个题解利用了动态规划的思想与最后一次出现位置的记录来计算字符串的总引力。定义 sum_g 为到当前字符为止的所有子字符串的引力总和，ans 为到目前为止所有字符产生的引力总和。遍历字符串的每个字符，更新当前字符的最后出现位置。对于每个字符 c，在位置 i，计算新增引力 sum_g += i - last.get(c, -1)，其中 last.get(c, -1) 给出字符 c 上一次出现的位置（如果没有出现过则为 -1）。然后将 sum_g 累加到答案 ans 中。这种方法有效地避免了对每个子字符串进行单独的引力计算，降低了计算复杂度。

时间复杂度: O(n)

空间复杂度: O(min(n, 26))

# 增加了详细注释的题解代码

class Solution:
    def appealSum(self, s: str) -> int:
        ans, sum_g, last = 0, 0, {}  # 初始化总引力、当前引力和字符最后出现位置的字典
        for i, c in enumerate(s):  # 遍历字符串中的每个字符及其索引
            sum_g += i - last.get(c, -1)  # 更新当前字符到目前为止的子字符串的引力总和
            ans += sum_g  # 将当前计算的引力总和加到总引力上
            last[c] = i  # 更新当前字符的最后出现位置
        return ans  # 返回最终计算的总引力

Explore

在这个题解中，动态规划的状态是通过变量 sum_g 来定义的，它表示包含当前字符 c 的所有子字符串的引力总和。这个状态在每一个字符的处理中被更新，以便计算出从字符串开始到当前字符为止的所有可能子字符串的引力总和。状态转移则是通过考虑当前字符最后一次出现位置与之前的出现位置之间的差异来进行，这样每次仅需更新一次状态，即可得到包含当前字符的所有子字符串的新增引力。

这个表达式中，`i` 是当前字符 c 的索引，而 `last.get(c, -1)` 返回字符 c 上一次出现的位置，默认为 -1 如果之前未出现过。表达式 `i - last.get(c, -1)` 计算的是从上一次字符 c 出现的位置后一个位置到当前位置的距离，这个距离正好等于以当前字符 c 结尾的、包含字符 c 的所有新子字符串的数量。因此，sum_g 加上这个值表示将这些新子字符串的引力加到总引力中。

更新字符的最后出现位置是为了记录这个字符最近一次出现的位置，这样在下次该字符再次出现时，可以计算出自上次出现以来新增的子字符串数量。一旦我们更新了这个位置，之前的出现位置对于未来的计算就不再有直接的影响，因为我们只关心最后一次出现到当前位置的新子字符串。因此，每次只需考虑当前的字符和它的最新出现位置，不需要回溯处理旧的出现位置。

此方法的效率与字符串中字符的重复性没有直接关系，因为无论字符是否重复，算法都是线性遍历每个字符并更新状态。每次更新操作的时间复杂度是常数级的，所以总的时间复杂度依然是 O(n)，其中 n 是字符串的长度。因此，即便字符串中重复字符很多，也不会对性能造成负面影响。这种方法的效率主要受到字符串长度的影响，而非字符的重复性。