class Solution {
public:
long long appealSum(string s) {
}
};
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 <= 105s 由小写英文字母组成原站题解
cpp 解法, 执行用时: 20 ms, 内存消耗: 10.3 MB, 提交时间: 2023-06-01 09:53:08
// 每个字符统计贡献
class Solution {
public:
long long appealSum(string s) {
vector<int> lasts(26, -1);
long long res = 0;
for(int i = 0; i < s.size(); ++i) {
res += 1ll * (i - lasts[s[i] - 'a']) * ((int)s.size() - i);
lasts[s[i] - 'a'] = i;
}
return res;
}
};
python3 解法, 执行用时: 248 ms, 内存消耗: 20.5 MB, 提交时间: 2023-06-01 09:52:42
'''
dp记录每个下标元素作为子序列尾部的总引力, 哈希表记录每个元素出现的最大下标
当前下标为i,上一个元素下标为j时, 子序列起始下标在[0, j]之间时引力不变, [j + 1, i]之间时引力 + 1
所以dp的转移方程 dp[i + 1] = dp[i] + i - j
如此即可求解.
'''
class Solution:
def appealSum(self, s: str) -> int:
l = len(s)
dp = [0 for i in range(l + 1)]
d = {}
for i, n in enumerate(s):
dp[i + 1] = dp[i] + i - d.get(n, -1) #当不存在j时,j为-1
d[n] = i
return sum(dp)
golang 解法, 执行用时: 4 ms, 内存消耗: 5.2 MB, 提交时间: 2023-06-01 09:51:35
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
}
java 解法, 执行用时: 6 ms, 内存消耗: 43 MB, 提交时间: 2023-06-01 09:51:24
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;
}
}
python3 解法, 执行用时: 156 ms, 内存消耗: 16.6 MB, 提交时间: 2023-06-01 09:51:04
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