2262-字符串的总引力

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

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

提示 1-1

将所有子串按照其末尾字符的下标分组。

提示 1-2

考虑两组相邻的子串：以 s[i-1] 结尾的子串、以 s[i] 结尾的子串。

提示 1-3

以 s[i] 结尾的子串，可以看成是以 s[i-1] 结尾的子串，在末尾添加上 s[i] 组成。

上面这一串提示是思考子串统计类问题的通用技巧之一。

提示 2-1

从左往右遍历 s，考虑将 s[i] 添加到以 s[i-1] 结尾的子串的末尾。添加后，这些以 s[i-1] 结尾的子串的引力值会增加多少？

提示 2-2

分类讨论：

  • 如果 s[i] 之前没有遇到过，那么这些子串的引力值都会增加 1，这些子串的引力值之和会增加 i，再加上 1，即 s[i] 单独组成的子串的引力值；
  • 如果 s[i] 之前遇到过，设其上次出现的下标为 j，那么向子串 s[0..i-1],\ s[1..i-1],\ s[2..i-1],\cdots,s[j..i-1] 的末尾添加 s[i] 后，这些子串的引力值是不会变化的，因为 s[i] 已经在 s[j] 处出现过了；而子串 s[j+1..i-1],\ s[j+2..i-1],\cdots,s[i-1..i-1] 由于不包含字符 s[i]，这些子串的引力值都会增加 1，因此有 i-j-1 个子串的引力值会增加 1，这些子串的引力值之和会增加 i-j-1，再加上 1，即 s[i] 单独组成的子串的引力值。

提示 2-3

模拟上述过程，遍历 s 的过程中用一个变量 sumG 维护以 s[i] 结尾的子串的引力值之和，同时用一个数组或哈希表 last 记录每个字符上次出现的下标。

累加遍历中的 sumG 即为答案（根据提示 1-1）。

[sol1-Python3]
1
2
3
4
5
6
7
8
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)  # 将提示 2-2 中的两种情况合并成一个公式
            ans += sum_g
            last[c] = i
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public long appealSum(String s) {
        var ans = 0L;
        var last = new int[26];
        Arrays.fill(last, -1); // 初始化成 -1 可以让提示 2-2 中的两种情况合并成一个公式
        for (int i = 0, sumG = 0; i < s.length(); i++) {
            var c = s.charAt(i) - 'a';
            sumG += i - last[c];
            ans += sumG;
            last[c] = i;
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    long long appealSum(string &s) {
        long ans = 0L;
        vector<int> last(26, -1); // 初始化成 -1 可以让提示 2-2 中的两种情况合并成一个公式
        for (int i = 0, sum_g = 0; i < s.length(); ++i) {
            char c = s[i] - 'a';
            sum_g += i - last[c];
            ans += sum_g;
            last[c] = i;
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
func appealSum(s string) (ans int64) {
	sumG, last := 0, [26]int{}
	for i := range last { last[i] = -1 } // 初始化成 -1 可以让提示 2-2 中的两种情况合并成一个公式
	for i, c := range s {
		c -= 'a'
		sumG += i - last[c]
		ans += int64(sumG)
		last[c] = i
	}
	return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 s 的长度。
  • 空间复杂度：O(|\Sigma|)，其中 |\Sigma| 为字符集合的大小，本题中字符均为小写字母，所以 |\Sigma|=26。

相似题目

最后

欢迎关注我的B站频道：灵茶山艾府 ，定期更新算法讲解视频哦~

 Comments
On this page
2262-字符串的总引力