6 用变化量分析法解决子串问题

2262. 字符串的总引力

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 6 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

难度：🔴困难

标签：#哈希表字符串动态规划

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

例如，"abbca" 的引力为 3，因为其中有 3 个不同字符 'a'、'b' 和 'c'。

给你一个字符串 s ，返回 其所有子字符串的总引力 。

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

输入: 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 0^{5}$ ，无法暴力枚举。

要求计算所有子串的总引力，对这类“所有子串”类问题，通常按结尾字符分组。

例如，"code" 可分为：

以 'c' 结尾："c"
以 'o' 结尾："co"，"o"
以 'd' 结尾："cod"，"od"，"d"
以 'e' 结尾：略

将以 s[i] 结尾的一系列子串记为 sub[i]，考虑 sub[i - 1] 与 sub[i] 的关系：

sub[i - 1] 的每个串加上一个字符 s[i] 就得到 sub[i] 中的串（额外的一个是长为 1 的 "s[i]"）这就要讨论加上的字符 s[i] 对 sub[i - 1] 中串的引力的影响：

如果 s[i] 之前未出现，sub[i - 1] 中的所有串的引力值都加 1。
如果 s[i] 之前出现的位置为 j，向 j 之后的子串加上 s[i]，其引力值不变，向 j 之前的子串加上 s[i]，其引力值加 1。

定义之前出现的字符的 j 为 -1，用一个 int[26] 维护 j，sub[i] 为 sub[i - 1] + i - j。

用 pre 表示 sub[i]，遍历 s，更新 pre 并将其累加到 ans。

复杂度

时间复杂度： $O (N)$
空间复杂度： $O (26)$

代码

Java

class Solution {
    public long appealSum(String s) {
        int[] last = new int[26];
        Arrays.fill(last, -1); // 还未出现, 为 -1
        long pre = 0, ans = 0;
        for (int i = 0; i < s.length(); i++) {
            pre += i - last[s.charAt(i) - 'a'];
            last[s.charAt(i) - 'a'] = i;
            ans += pre;
        }
        return ans;
    }
}

Python

class Solution:
    def appealSum(self, s: str) -> int:
        last, pre, ans = {}, 0, 0
        for i, c in enumerate(s):
            pre += i - last.get(c, -1) # 还未出现, 为 -1
            last[c] = i
            ans += pre
        return ans

最后

更多系列「外源推文」&「生活分享」关注公众号：

🥑 EmberNecro

Explorer