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

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成。

解题思路

这道题要求计算所有子字符串的引力值总和。暴力枚举所有子字符串会超时，需要找到更高效的解法。

核心思路：动态规划 + 贡献法

关键观察：考虑每个字符对总引力值的贡献。对于位置 i 的字符 c，我们需要计算有多少个以位置 i 结尾的子字符串包含字符 c。

算法步骤：

  1. 用 dp[i] 表示以位置 i 结尾的所有子字符串的引力值总和
  2. 用 last[c] 记录字符 c 上一次出现的位置
  3. 对于位置 i 的字符 c：
    • 包含字符 c 的以位置 i 结尾的子字符串有 last[c] + 1 个（从位置 0 到 last[c] 的任意起点都可以）
    • 转移方程：dp[i] = dp[i-1] + last[c] + 1
    • 更新 last[c] = i

这种方法避免了重复计算，每个字符的贡献被准确统计。时间复杂度为 O(n)，空间复杂度为 O(1)。

优化： 实际实现中不需要 dp 数组，只需要维护当前的总引力值即可。

代码实现

class Solution {
public:
    long long appealSum(string s) {
        long long result = 0, current = 0;
        vector<int> last(26, -1);
        
        for (int i = 0; i < s.length(); i++) {
            int c = s[i] - 'a';
            current += last[c] + 1;
            last[c] = i;
            result += current;
        }
        
        return result;
    }
};

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

public class Solution {
    public long AppealSum(string s) {
        long result = 0, current = 0;
        int[] last = new int[26];
        Array.Fill(last, -1);
        
        for (int i = 0; i < s.Length; i++) {
            int c = s[i] - 'a';
            current += last[c] + 1;
            last[c] = i;
            result += current;
        }
        
        return result;
    }
}

var appealSum = function(s) {
    let result = 0, current = 0;
    let last = new Array(26).fill(-1);
    
    for (let i = 0; i < s.length; i++) {
        let c = s.charCodeAt(i) - 97;
        current += last[c] + 1;
        last[c] = i;
        result += current;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历字符串一次，每次操作为常数时间
空间复杂度O(1)只使用固定大小的数组存储26个字母的最后出现位置

相关题目