828. 统计子串中的唯一字符

发表于 2026-01-16 分类于力扣阅读次数： Waline：本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

子数组的状态转移方程

思路

变量约定（与代码完全一致）

字符串下标采用 1-based
i：当前子串的右端点
f：所有 以位置 i−1 结尾 的子串的唯一字符数总和
t：所有 以位置 i 结尾 的子串的唯一字符数总和
pre0[c]：字符 c 更早一次出现的位置（older）
pre1[c]：字符 c 次早一次出现的位置（newer）
若不存在，则对应位置为 0

一、问题建模

定义： \[ f_i = \text{所有以位置 } i \text{ 结尾的子串的唯一字符数总和} \] 目标即为： \[ \text{Answer} = \sum_{i=1}^{n} f_i \] 因此关键问题是： 如何从 \(f_{i-1}\) 快速推导出 \(f_i\)。

二、单字符在状态转移中的贡献变化

考虑当前位置 \(i\)，字符为 \(c = s[i]\)。

该字符之前的出现情况由 pre0[c] 和 pre1[c] 描述：

pre1[c]：最近一次出现位置
pre0[c]：再之前一次出现位置

字符 \(c\) 在位置 \(i\) 的出现，只会影响那些 以 \(i\) 结尾的子串，并且其影响完全由这两个位置决定。

三、统一的状态增量公式（核心）

从 \(f\) 到 \(t\) 的转移中，字符 \(c\) 产生的净增量为： \[ \Delta = (i - \text{pre1}[c]) - (\text{pre1}[c] - \text{pre0}[c]) \] 于是整体状态转移为： \[ t = f + \Delta \]

增量公式的解释

我们解释下面这一条公式为什么成立： \[ \Delta = (i - \text{pre1}[c]) - (\text{pre1}[c] - \text{pre0}[c]) \] 即： \[ t = f + (i - \text{pre1}[c]) - (\text{pre1}[c] - \text{pre0}[c]) \]

一、作图

将字符串的位置看成一条数轴，用“点”表示字符 c 的出现位置：

位置轴（1-based）：

|----●----------●-----------●---->
     pre0        pre1          i

pre0[c]：字符 c 更早一次出现
pre1[c]：字符 c 次早一次出现
i：当前出现位置

我们只关心 “右端点固定为 i 的子串”。

二、哪些子串中，字符 c 是唯一的？

对于任意以 i 结尾的子串，其左端点记为 L。

情况划分（只看字符 c）

1️⃣ `L > pre1`

|----●----------●===========●
     pre0        pre1        i
                  ↑         ↑
                  L         i

子串 [L, i] 中只包含 当前位置 i 的 c
字符 c 是唯一字符
这样的 L 一共有：

\[ i - \text{pre1} \]

👉 这是“新产生的唯一贡献”

2️⃣ `pre0 < L ≤ pre1`

|----●==========●-----------●
     pre0        pre1        i
          ↑      ↑
          L      pre1

子串 [L, i] 中包含 pre1 和 i 两个 c
字符 c 不再唯一
但在上一步（右端点为 i-1）时：
- pre1 还是唯一的

这些子串数量是： \[ \text{pre1} - \text{pre0} \] 👉 这是“需要被扣除的旧贡献”

3️⃣ `L ≤ pre0`

1 2	\|====●----------●-----------● pre0 pre1 i

子串中至少有 三个 c
在 i-1 时就已经不是唯一
对 f → t 没有任何变化

三、用点阵图合并三种情况

把上面的分析合并到一张图中：

L 的可选区间（右端点固定为 i）：

|====|==========|===========|
     pre0       pre1        i
      无变化     被扣除       新增

对应数量：

区间	子串数量	对 f→t 的影响
`L ≤ pre0`	任意	0
`pre0 < L ≤ pre1`	`pre1 - pre0`	−
`L > pre1`	`i - pre1`	+

四、增量公式的来源（从点阵直接读）

将“新增”与“扣除”合并： \[ \Delta = (\text{新增唯一}) - (\text{失效唯一}) \] 这正是代码中的那一行：

1	t += i - pre1[d] - (pre1[d] - pre0[d]);

四、三种出现情况在代码中的自然展开

由于初始值为 0，上述统一公式在代码中会自然分裂成三种情况：

1. 第一次出现（`pre0[c] == 0`）

此时： \[ \text{pre1}[c] = 0,\quad \text{pre0}[c] = 0 \] 增量为： \[ \Delta = i \] 对应代码：

1 2	t += i; pre0[c] = i;

2. 第二次出现（`pre1[c] == 0`）

此时： \[ \text{pre1}[c] = 0,\quad \text{pre0}[c] = p \] 代入统一公式： \[ \Delta = (i - p) - (p - 0) = i - 2p \] 对应代码：

1 2	t += i - 2 * pre0[c]; pre1[c] = i;

3. 第三次及以后（`pre0[c]` 与 `pre1[c]` 均非零）

此时： \[ \text{pre1}[c] = p,\quad \text{pre0}[c] = q \] 增量为： \[ \Delta = (i - p) - (p - q) \] 并将出现位置整体右移：

1
2
3

t += i - pre1[c] - (pre1[c] - pre0[c]);
pre0[c] = pre1[c];
pre1[c] = i;

五、完整状态转移流程

在每个位置 \(i\)：

令 t = f
根据字符 s[i] 的历史位置计算增量并更新 t
将 t 累加进答案
更新 f = t

时间复杂度为 \(O(n)\)，空间复杂度为 \(O(26)\)。

六、AC 代码（逐行注释，与建模完全一致）

class Solution {
public:
    int uniqueLetterString(string s) {
        int n = s.size();

        // f : 所有以 i-1 结尾的子串的唯一字符数总和
        // ans : 最终答案
        int f = 0, ans = 0;

        // pre0[d] : 字符 d 更早一次出现的位置
        // pre1[d] : 字符 d 次早一次出现的位置
        // 1-based，下标为 0 表示未出现
        int pre0[26] = {}, pre1[26] = {};

        for (int i = 1; i <= n; ++i) {
            int t = f;
            int d = s[i - 1] - 'A';

            if (pre0[d] == 0) {
                // 第一次出现
                t += i;
                pre0[d] = i;
            }
            else if (pre1[d] == 0) {
                // 第二次出现
                t += i - 2 * pre0[d];
                pre1[d] = i;
            }
            else {
                // 第三次及以后
                t += i - pre1[d] - (pre1[d] - pre0[d]);
                pre0[d] = pre1[d];
                pre1[d] = i;
            }

            ans += t;
            f = t;
        }

        return ans;
    }
};

七、总结

本算法以 子串右端点 为 DP 维度
每个字符的贡献变化只依赖 pre0 / pre1
所有分支本质上都是统一公式的展开
避免枚举子串，实现线性复杂度

考点

思路