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⁵
s 由小写英文字母组成

解法

方法一：枚举

我们可以枚举以每个字符 \(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\)。继续遍历直到字符串结束。

Python3JavaC++GoTypeScript

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

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

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

func appealSum(s string) int64 {
    var ans, t int64
    pos := make([]int, 26)
    for i := range pos {
        pos[i] = -1
    }
    for i, c := range s {
        c -= 'a'
        t += int64(i - pos[c])
        ans += t
        pos[c] = i
    }
    return ans
}

function appealSum(s: string): number {
    const pos: number[] = Array(26).fill(-1);
    const n = s.length;
    let ans = 0;
    let t = 0;
    for (let i = 0; i < n; ++i) {
        const c = s.charCodeAt(i) - 97;
        t += i - pos[c];
        ans += t;
        pos[c] = i;
    }
    return ans;
}

2262. 字符串的总引力

题目描述

解法

方法一：枚举

评论