2262. 字符串的总引力

题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/total-appeal-of-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

参考「这里」的方法。

表示以结尾的子串的引力值，例如，对于字符串cacba，dp[4]表示以第二个a结尾的子串的引力值之和，考虑dp[4]和dp[3]的关系：

增加了下标4处的a，对于前面的子串cb和b，引力值会各自加1，对于acb和cacb子串就不会加1，因为a已经出现过了。

一般地，考虑和的关系，就是在考虑添加后引力值可以增加多少，即贡献了多少引力值。按照前面的思路，对于，找到其上一次出现的下标，对于这个子串加上后引力值会加，因此这些子串的引力值在基础上加就是的一部分，另外，s[i]单独作为子串，引力值也算1，因此，其中表示上一次出现的位置。

最终返回的是sum(dp)。

代码

DP O(n)空间

class Solution {
    public long appealSum(String s) {
        int n = s.length();
        long ans = 0;
        int[] pre = new int[26];
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            char c = s.charAt(i - 1);
            dp[i] = dp[i - 1] + i - pre[c - 'a'];
            ans += dp[i];
            pre[c - 'a'] = i;
        }
        return ans;
    }
}

DP O(1)空间

dp[i]只和dp[i-1]有关，因此可以使用一个sum变量代替数组。

class Solution {
    public long appealSum(String s) {
        int n = s.length();
        long ans = 0;
        int[] pre = new int[26];
        Arrays.fill(pre, -1);
        long sum = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            sum += i - pre[c - 'a'];
            ans += sum;
            pre[c - 'a'] = i;
        }
        return ans;
    }
}