2262. 字符串的总引力

发表于 分类于 阅读次数： Waline： 本文字数： 772 阅读时长 ≈ 3 分钟

考点

  • 线性DP
  • 状态转移方程的设计

思路

一、问题描述

给定一个长度为 \(n\) 的字符串 \(s\)，定义任意子串的 appeal 为该子串中 不同字符的个数（distinct characters）。

目标是计算： \[ \sum_{\text{所有子串 } s[l..r]} \text{appeal}(s[l..r]) \] 其中 \(0 \le l \le r < n\)，且 \(n \le 10^5\)。

二、朴素思路及其瓶颈

对于每个右端点 \(r\)，枚举所有左端点 \(l\)，并重新统计子串 \(s[l..r]\) 的 distinct 字符数：

  • 子串总数为 \(O(n^2)\)
  • 每个子串若再统计字符，复杂度更高

因此朴素做法不可行。

关键问题在于： 是否真的需要对每个子串“重新统计”？

三、核心建模思想：从“子串”转为“贡献”

3.1 固定右端点的视角

将所有子串按右端点分类。

设：

  • 右端点为 \(i\)（使用 1-based 下标）

  • 所有以 \(i\) 结尾的子串为： \[ s[1..i],\ s[2..i],\ \dots,\ s[i..i] \] 共 \(i\) 个

定义： \[ f(i) = \sum_{l=1}^{i} \text{appeal}(s[l..i]) \] 那么最终答案就是： \[ \sum_{i=1}^{n} f(i) \]

3.2 关键问题转化

从 \(i-1\) 推到 \(i\) 时，只新增了一个字符 \(s[i]\)。

问题转化为：

当字符 \(s[i]\) 加入后， 在所有以 \(i\) 结尾的子串中，有多少个子串的 appeal 会增加 1？

四、单字符贡献的精确刻画

设当前字符为 \(c = s[i]\)。

定义：

  • \(\text{last}[c]\)：字符 \(c\) 上一次出现的位置（1-based）
  • 若从未出现过，则 \(\text{last}[c] = 0\)

4.1 哪些子串会因为 \(c\) 而 appeal +1？

考虑所有以 \(i\) 结尾的子串 \(s[l..i]\)：

  • 若 \(l \le \text{last}[c]\)： 子串中已经包含 \(c\)，appeal 不变
  • 若 \(l > \text{last}[c]\)： 子串中第一次出现 \(c\)，appeal +1

因此，新增贡献的子串数量为： \[ i - \text{last}[c] \]

4.2 状态转移方程（核心）

由此得到极其简洁的状态转移： \[ \boxed{ f(i) = f(i-1) + \bigl(i - \text{last}[s[i]]\bigr) } \] 并在计算完后更新： \[ \text{last}[s[i]] \leftarrow i \]

五、整体算法流程

  1. 使用数组 last[26] 记录每个字符上一次出现的位置（初始化为 0）
  2. 用变量 f 表示当前的 \(f(i)\)
  3. 用变量 ans 累加所有 \(f(i)\)
  4. 单次从左到右扫描字符串

六、复杂度分析

  • 时间复杂度： \[ O(n) \]

  • 空间复杂度： \[ O(1) \quad (\text{字符集大小为常数}) \]

七、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    const int maxn = 1e5 + 5;

    long long appealSum(string s) {
        int n = s.size();

        // f 表示当前 f(i)：所有以 i 结尾的子串的 appeal 之和
        long long f = 0;

        // ans 为最终答案
        long long ans = 0;

        // lst[c] 表示字符 c 上一次出现的位置（1-based）
        // 初始为 0，表示从未出现
        int lst[26] = {};

        // i 使用 1-based 下标，便于公式书写
        for (int i = 1; i <= n; ++i) {
            int c = s[i - 1] - 'a';

            // 新字符 s[i] 对 f(i) 的新增贡献
            // 等于 i - 上一次出现位置
            f += i - lst[c];

            // 更新该字符最近出现的位置
            lst[c] = i;

            // 累加到总答案
            ans += f;
        }

        return ans;
    }
};