2262. 字符串的总引力

🔴   🔖  哈希表 字符串 动态规划  🔗 力扣 LeetCode

题目

The appeal of a string is the number of distinct characters found in the string.

• For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.

Given a string s, return the total appeal of all of its substrings.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "abbca"

Output: 28

Explanation: The following are the substrings of "abbca":

• Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
• Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
• Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7.
• Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6.
• Substrings of length 5: "abbca" has an appeal of 3. The sum is 3.

The total sum is 5 + 7 + 7 + 6 + 3 = 28.

Example 2:

Input: s = "code"

Output: 20

Explanation: The following are the substrings of "code":

• Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
• Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6.
• Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6.
• Substrings of length 4: "code" has an appeal of 4. The sum is 4.

The total sum is 4 + 6 + 6 + 4 = 20.

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

题目大意

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

例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 'c' 。 给你一个字符串 s ，返回 其所有子字符串的总引力 。

子字符串 定义为：字符串中的一个连续字符序列。

解题思路

对于每个字符，它会出现在某些子字符串中，并对这些子字符串的吸引力有贡献。可以跟踪每个字符最后一次出现的位置，并计算从该字符的最后出现位置到当前字符之间的子字符串的吸引力变化。

为了避免遍历所有子字符串，可以使用动态更新的方式计算某个字符对当前子字符串的贡献。通过记录每个字符最后一次出现的位置，可以快速计算该字符的贡献。

1. 初始化：

   • 使用数组 lastIndex 来记录每个字符的最后一次出现位置，初始值设为 -1，表示还没有出现过。
   • 变量 dp 用来跟踪从第一个字符到当前字符的所有子字符串的总吸引力。
   • 变量 res 用来存储所有子字符串的吸引力总和。

2. 遍历字符串：

   • 对于字符串中的每个字符，首先通过 lastIndex 找到该字符上一次出现的位置。如果当前字符上一次出现在位置 j，那么从 j+1 到 i 的所有子字符串都会包含当前字符，因此当前字符对这些子字符串的吸引力都有贡献。
   • 计算当前字符的贡献并更新 dp 和 res。

3. 更新索引：

   • 每次处理完当前字符后，将其最后出现的位置更新为当前索引 i。

复杂度分析

• 时间复杂度： O(n)，因为只遍历了一遍字符串，且每个字符的操作都是常数时间。
• 空间复杂度： O(1)（考虑字符集大小为 26 个字母）。

通过记录每个字符的最后出现位置，可以高效地计算出每个字符对总吸引力的贡献，避免了暴力遍历所有子字符串的复杂度，从而达到了线性时间的复杂度。

代码

/**
 * @param {string} s
 * @return {number}
 */
var appealSum = function (s) {
	let res = 0,
		dp = 0;
	// 用于记录每个字符最后一次出现的位置
	let lastIndex = new Array(26).fill(-1);
	for (let i = 0; i < s.length; i++) {
		// 将字符转换为数组索引
		let charIndex = s[i].charCodeAt() - 'a'.charCodeAt();
		// 更新当前子串的总吸引力
		dp += i - lastIndex[charIndex];
		// 累加到总吸引力
		res += dp;
		// 更新字符的最后出现位置
		lastIndex[charIndex] = i;
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
828	统计子串中的唯一字符		哈希表 字符串 动态规划
2062	统计字符串中的元音子字符串		哈希表 字符串
2063	所有子字符串中的元音		数学 字符串 动态规划 1+
3134	找出唯一性数组的中位数		数组 哈希表 二分查找 1+