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

2023-03-20 HGNULB 约 13 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

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

题意分析

定义 $countUniqueChars(t)$ 为字符串 $t$ 中恰好只出现一次的字符的个数。给定字符串 s，求它所有子串（连续、非空，按位置区分而不去重）的 $countUniqueChars$ 之和。

「唯一」要读准：不是「不同字符的种类数」，而是出现次数恰好为 1 的字符个数。以 ABA 为例，它的不同字符有 2 种（A 和 B），但只出现一次的字符只有 B 一个，所以 $countUniqueChars(\texttt{ABA}) = 1$。这两个概念混淆是这道题最早的岔路口。

「子串按位置区分」也很关键：ABA 里两个 A 是两个不同的子串，各自贡献 1。所以不能对子串内容去重。

约束是 $1 \le s \le 10^5$，全部为大写英文字母。子串数量是 $O(n^2) \approx 5 \times 10^9$，逐个枚举子串再统计必然超时，即便把统计优化成 $O(1)$ 也不行。这个规模直接排除了「枚举子串」这个维度，逼你换一个求和顺序。

字符集只有 26 个，这是一个很强的暗示：允许对每种字符单独开数组做记录，$26n$ 的辅助工作是免费的。

边界方面：单字符串的答案是 1；全部字符相同的串（如 AAAA）的答案等于 $n$（只有长度为 1 的子串里 A 是唯一的）；全部字符互不相同的串答案是所有子串的长度之和。这些都应由统一的公式得出。

解法：按字符贡献计数（前后出现位置）

核心思路

暴力做法是枚举左右端点得到每个子串，再数一遍其中只出现一次的字符。这是 $O(n^3)$；用滑动的计数数组优化成边扩展边维护，也还是 $O(26 n^2)$。瓶颈很清楚：子串的数量本身就是 $O(n^2)$，只要还在按子串枚举，就没有出路。

突破口是交换求和顺序。原式是「对每个子串，数它里面有几个唯一字符」，把它翻转成「对每个字符的每次出现，数它在多少个子串里是唯一的」。两种数法数的是同一批「(子串, 唯一字符)」二元组，所以总和相等；但后者的枚举对象只有 $n$ 个（每个位置一次出现），一下就把规模从 $O(n^2)$ 压到了 $O(n)$。这个「按贡献计数」的视角转换，是本题的全部难度所在。

现在固定一个位置 $i$，设 $s[i]$ 这个字符上一次出现在 $prev$、下一次出现在 $next$（不存在时分别取 $-1$ 和 $n$）。问：有多少个子串 $[l, r]$ 使得 $s[i]$ 在其中恰好出现一次？条件是三条：$l \le i \le r$（包含位置 $i$）、$l > prev$（不能把上一个同字符括进来）、$r < next$（不能把下一个同字符括进来）。

于是 $l$ 的取值范围是 $(prev, i]$，共 $i - prev$ 种；$r$ 的取值范围是 $[i, next)$，共 $next - i$ 种。两者独立，所以位置 $i$ 的贡献是

$(i - prev) \times (next - i)$

把所有位置的贡献加起来就是答案。注意这里只需要看同一字符最近的前后各一次出现，更远的同字符会被这两个更近的挡住，完全不影响计数——这正是公式如此简洁的原因。

剩下的问题是如何拿到每个位置的 $prev$ 和 $next$。最直白的办法是预处理两个长度为 $n$ 的数组。但有一个更省的技巧：延迟结算。一边从左往右扫描，一边为每个字符维护它最近两次出现的位置——记为 $prev[c]$（最近一次）和 $prevPrev[c]$（次近一次）。当扫描到位置 $i$ 且 $s[i] = c$ 时，我们恰好知道了 $prev[c]$ 这次出现的 next 就是 $i$，于是立刻结算它的贡献：

$(prev[c] - prevPrev[c]) \times (i - prev[c])$

结算完再把两个变量向前滚动：$prevPrev[c] \leftarrow prev[c]$、$prev[c] \leftarrow i$。

这样每次出现的贡献都在「下一次同字符出现时」被结算。扫描结束后，每种字符最后一次出现还没被结算（它没有下一次），需要在收尾阶段用 $next = n$ 补上。这就是代码里那个额外的 26 次循环的用途。

维持的不变量是：扫描到位置 $i$ 之前，所有在 $i$ 之前出现过、且后面还有同字符出现的位置，其贡献都已计入答案；每种字符的 $prev$ 与 $prevPrev$ 分别是它在 $[0, i)$ 中最近与次近的出现位置（不足则为 $-1$）。

用 $-1$ 作为「不存在」的哨兵，让公式无需特判：当 $prevPrev = -1$ 时，$prev - prevPrev = prev + 1$，正是左端点可以从 0 开始取到 $prev$ 的方案数，语义完全正确。

解题步骤

第一步，为 26 个字符各准备 $prev$ 与 $prevPrev$ 两个位置变量，全部初始化为 $-1$。 为什么哨兵取 $-1$ 而不是 0：左端点的可选数量是 $i - prev$，当该字符此前从未出现时左端点可以取 $0$ 到 $i$ 共 $i+1$ 种，代入 $prev = -1$ 恰好得到 $i + 1$。取 0 会少算一种。

第二步，从左往右扫描，取当前字符 $c$。

第三步，若 $prev[c] \ne -1$，结算 $prev[c]$ 这次出现的贡献：$(prev[c] - prevPrev[c]) \times (i - prev[c])$。 为什么此刻才结算：贡献公式需要 $next$，而 $prev[c]$ 的 $next$ 直到当前位置 $i$ 出现同字符时才确定。这种「等到信息齐了再算」的延迟结算，省掉了预处理 $next$ 数组的那一遍扫描和 $O(n)$ 空间。为什么要判 $prev[c] \ne -1$：该字符还没出现过时无可结算。

第四步，滚动更新 $prevPrev[c] \leftarrow prev[c]$、$prev[c] \leftarrow i$。 为什么顺序不能反：先写 $prev[c] \leftarrow i$ 会让旧的 $prev$ 丢失，$prevPrev$ 拿到的是 $i$ 自己，之后所有公式全错。

第五步，扫描结束后遍历 26 个字符，对每个出现过的字符结算它最后一次出现的贡献，此时 $next = n$：$(prev[c] - prevPrev[c]) \times (n - prev[c])$。 为什么必须有这一步：每种字符的最后一次出现在主循环里永远等不到「下一次同字符」，不补算就会整体漏掉最多 26 项贡献。为什么 $next$ 取 $n$：右端点最大只能是 $n-1$，把虚拟的下一次出现放在 $n$ 处，方案数 $n - prev$ 恰好是 $prev$ 到 $n-1$ 的个数。

第六步，返回累加结果。 为什么用 64 位累加：单项贡献最大可达 $O(n^2)$ 量级（例如某字符只出现一次时是 $n \times 1$ 到 $\frac{n^2}{4}$），虽然本题最终答案在 32 位范围内，但中间累加用 64 位更稳妥。

以 s = "ABA" 走一遍（$n = 3$，期望答案 8）。字符 A 记作 0、B 记作 1。初始 $prev$ 与 $prevPrev$ 全为 $-1$。

$i = 0$，字符 A：$prev[A] = -1$，没有可结算的前一次出现，跳过。滚动：$prevPrev[A] = -1$、$prev[A] = 0$。

$i = 1$，字符 B：$prev[B] = -1$，跳过。滚动：$prevPrev[B] = -1$、$prev[B] = 1$。

$i = 2$，字符 A：$prev[A] = 0 \ne -1$，结算位置 0 这次 A 的贡献。此刻我们知道位置 0 的 A 的下一次出现就是 $i = 2$，而它的上一次出现是 $prevPrev[A] = -1$。贡献 $= (0 - (-1)) \times (2 - 0) = 1 \times 2 = 2$。答案累计 2。含义是：包含位置 0 的 A 且不含位置 2 的 A 的子串有 $l \in {0}$、$r \in {0, 1}$ 共 2 个，即 A 和 AB，在这两个子串里位置 0 的 A 都是唯一的。滚动：$prevPrev[A] = 0$、$prev[A] = 2$。

收尾循环：
字符 A：$prev[A] = 2$、$prevPrev[A] = 0$，$next$ 取 $n = 3$。贡献 $= (2 - 0) \times (3 - 2) = 2 \times 1 = 2$。答案累计 4。含义是：包含位置 2 的 A 且不含位置 0 的 A 的子串有 $l \in {1, 2}$、$r \in {2}$ 共 2 个，即 BA 和 A。
字符 B：$prev[B] = 1$、$prevPrev[B] = -1$，$next$ 取 3。贡献 $= (1 - (-1)) \times (3 - 1) = 2 \times 2 = 4$。答案累计 8。含义是：B 只出现一次，所有包含它的子串里它都是唯一的，$l \in {0, 1}$、$r \in {1, 2}$ 共 4 个，即 AB、ABA、B、BA。

返回 8。核对一下：ABA 的六个子串及其唯一字符数分别是 A(1)、B(1)、A(1)、AB(2)、BA(2)、ABA(1，只有 B 唯一)，合计 $1+1+1+2+2+1 = 8$，与按贡献求和的结果一致。

这个例子还顺带验证了两处哨兵的作用：位置 0 的 A 结算时用了 $prevPrev = -1$，字符 B 结算时同时用了 $prevPrev = -1$ 与 $next = n$，两处都不需要特判分支。

代码实现

class Solution {
    public int uniqueLetterString(String s) {
        int n = s.length();
        int[] prevPrev = new int[26];
        int[] prev = new int[26];
        Arrays.fill(prevPrev, -1);
        Arrays.fill(prev, -1);

        long answer = 0;
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'A';
            if (prev[c] != -1) {
                answer += (long) (prev[c] - prevPrev[c]) * (i - prev[c]);
            }
            prevPrev[c] = prev[c];
            prev[c] = i;
        }

        for (int c = 0; c < 26; c++) {
            if (prev[c] != -1) {
                answer += (long) (prev[c] - prevPrev[c]) * (n - prev[c]);
            }
        }
        return (int) answer;
    }
}

func uniqueLetterString(s string) int {
    n := len(s)
    prevPrev := make([]int, 26)
    prev := make([]int, 26)
    for i := 0; i < 26; i++ {
        prevPrev[i] = -1
        prev[i] = -1
    }

    var answer int64 = 0
    for i := 0; i < n; i++ {
        c := int(s[i] - 'A')
        if prev[c] != -1 {
            answer += int64(prev[c]-prevPrev[c]) * int64(i-prev[c])
        }
        prevPrev[c] = prev[c]
        prev[c] = i
    }

    for c := 0; c < 26; c++ {
        if prev[c] != -1 {
            answer += int64(prev[c]-prevPrev[c]) * int64(n-prev[c])
        }
    }
    return int(answer)
}

复杂度分析

时间复杂度：$O(n + \Sigma)$，其中 $\Sigma = 26$ 是字符集大小。主循环扫描每个位置一次，每次只做一次减法、一次乘法和两次赋值；收尾循环固定 26 次。相比枚举子串的 $O(n^2)$（$n = 10^5$ 时约 $5 \times 10^9$），这里只有十万次操作。

空间复杂度：$O(\Sigma)$，即两个长度为 26 的整型数组，与字符串长度无关。这比「预处理每个位置的前一次 / 后一次出现位置」的 $O(n)$ 空间写法更省——延迟结算把「需要 $next$」这个未来信息，转化成了「在下一次同字符出现时回头结算」的当下操作。

关键点总结

枚举对象过多时，交换求和顺序。原问题按子串求和有 $O(n^2)$ 项，按「字符的每次出现」求和只有 $O(n)$ 项，而两者数的是同一批二元组。这个「贡献法」是组合计数题的核心武器，凡是看到「对所有子串 / 子数组求某个统计量之和」，第一反应就该是它。

贡献区间由「最近的同类元素」界定。位置 $i$ 作为唯一出现的合法子串，左端点被上一次同字符卡住、右端点被下一次同字符卡住，方案数是两段长度的乘积。这个「左右各找最近的边界，相乘得贡献」的模式，与单调栈求子数组最小值之和是同一套骨架，只是边界的定义换了。

哨兵值让公式免于特判。$prev = -1$ 和 $next = n$ 分别表示「左边没有同字符」和「右边没有同字符」，代入乘法公式后自动给出正确的方案数。选哨兵时的标准是：代入公式后语义是否天然正确，而不是随便取个不可能的值。

延迟结算可以把「需要未来信息」变成「当下可算」。不预处理 $next$ 数组，而是在下一次同字符出现时回头结算上一次，把空间从 $O(n)$ 压到 $O(26)$。判断能否这么做的标准是：所需的未来信息是否会在扫描过程中的某个确定时刻自然出现。

延迟结算必须配一个收尾补算。每种字符的最后一次出现永远等不到「下一次」，必须在扫描结束后统一用虚拟的 $next = n$ 补上。凡是用延迟结算的写法，都要专门检查「有没有一批对象永远等不到触发条件」。

面试视角：这题的分水岭是能否说出「换成按每个字符的每次出现计算贡献」。说出来之后，$(i - prev) \times (next - i)$ 的推导只需要解释左右端点的取值范围。常见追问有三个：一是「为什么只看最近的前后各一次」，答更远的同字符被更近的挡住，不影响可行区间；二是「$prev = -1$ 时为什么不用特判」，答哨兵代入公式后语义正确；三是「能不能只用 $O(1)$ 额外空间」，答已经是 $O(26)$ 即常数级，且不需要预处理数组。如果面试官把「唯一字符」改成「出现恰好 $k$ 次的字符」，要能答出：需要维护每个字符最近 $k+1$ 次出现的位置，贡献公式相应变成两段跨度的乘积。

易错点总结

错误写法：把 $countUniqueChars$ 理解成「不同字符的种类数」。以 s = "ABA" 为例，若按种类数计算，子串 ABA 会贡献 2 而不是 1，总和变成 9，而正确答案是 8。题目要的是「出现次数恰好为 1」的字符个数。

错误写法：滚动更新时先写 $prev[c] \leftarrow i$ 再写 $prevPrev[c] \leftarrow prev[c]$。以 s = "ABA" 为例，$i = 2$ 处理完后 $prevPrev[A]$ 会变成 2 而不是 0，收尾时贡献算成 $(2-2) \times (3-2) = 0$，总和变成 6，而正确答案是 8。两个变量的滚动必须自后向前赋值。

错误写法：漏掉收尾的 26 次补算循环。以 s = "ABA" 为例，主循环只结算了位置 0 的 A，贡献 2；位置 2 的 A 和位置 1 的 B 都没有「下一次出现」来触发结算，最终返回 2，而正确答案是 8。延迟结算必然要配收尾补算。

错误写法：哨兵取 0 而不是 $-1$。以 s = "AB" 为例，正确答案是 4（A、B 各 1，AB 贡献 2）。哨兵取 0 时，A 的收尾贡献算成 $(0 - 0) \times (2 - 0) = 0$、B 的算成 $(1 - 0) \times (2 - 1) = 1$，返回 1。正确的算法用 $prevPrev = -1$ 得到 $1 \times 2 = 2$ 与 $2 \times 1 = 2$，合计 4。哨兵必须让「左端点可取到 0」这一种方案被计入。

错误写法：收尾时 $next$ 取 $n - 1$。以 s = "AB" 为例，字符 B 的贡献算成 $(1 - (-1)) \times (1 - 1) = 0$，直接漏掉，返回值偏小。右端点的可选个数是 $[prev, n-1]$ 共 $n - prev$ 个，虚拟的下一次出现位置应取 $n$。

错误写法：结算的是当前位置 $i$ 而不是 $prev[c]$。以 s = "ABA" 为例，$i = 2$ 时若结算的是位置 2 的贡献，用的 $next$ 就是当前的 $i$ 本身，得到 $(2 - 0) \times (2 - 2) = 0$，逻辑完全错乱。延迟结算结算的永远是上一次出现，因为它的 $next$ 才刚刚确定。

错误写法：贡献公式写成 $(i - prev) + (next - i)$（加法而非乘法）。以 s = "B" 为例，正确贡献是 $(0 - (-1)) \times (1 - 0) = 1$，写成加法得 $1 + 1 = 2$，返回 2 而正确答案是 1。左右端点的选择相互独立，方案数是乘法关系。

错误写法：只维护 $prev$ 而不维护 $prevPrev$。以 s = "ABA" 为例，结算位置 0 的 A 时需要知道它前面还有没有 A（这里没有，取 $-1$）；只有 $prev$ 的话，在结算时它已经指向被结算的那个位置本身，左端点范围无从计算。必须同时保留最近两次出现。

错误写法：用哈希表存每个字符的所有出现位置，再对每个位置去查前后邻居。以 $n = 10^5$ 的输入为例，这么做正确但要多花 $O(n)$ 空间存位置列表；更常见的问题是查前后邻居时下标偏移写错，比如把列表里的第 $t$ 个位置的前驱写成第 $t$ 个而不是第 $t-1$ 个。两个滚动变量已经足够。

错误写法：字符下标用 s.charAt(i) - 'a'。以 s = "ABA" 为例，大写 A 减去小写 a 得到 $-32$，数组下标为负，Java 抛越界异常，Go 直接 panic。题目明确是大写字母，必须减 'A'。

错误写法：用 32 位整型累加中间结果。以某字符只在字符串正中出现一次、$n = 10^5$ 的输入为例，单项贡献可达 $\frac{n}{2} \times \frac{n}{2} = 2.5 \times 10^9$，超出 32 位有符号整型上限而溢出成负数。累加要用 64 位，最后再转回。

错误写法：为每个子串维护滑动的字符计数数组，逐个统计。以 $n = 10^5$ 为例，子串数量是 $5 \times 10^9$，即便每个子串只花 $O(1)$ 也无法通过。必须换求和顺序，而不是优化子串内部的统计。

相似题目

题目	难度	考察点
907. 子数组的最小值之和	中等	同为贡献法，边界改由「左右两侧第一个更小元素」界定，需用单调栈求出
3. 无重复字符的最长子串	中等	同样关注字符的上一次出现位置，但用滑动窗口求最长而非累加贡献
992. K 个不同整数的子数组	困难	统计「恰好 K 种」的子数组个数，用「至多 K」减「至多 K-1」的差分技巧
1248. 统计「优美子数组」	中等	统计恰含 k 个奇数的子数组数，可用前缀和计数或同样的左右可选区间相乘
340. 至多包含 K 个不同字符的最长子串	中等	滑动窗口配合字符频次表，训练「字符出现次数」这一维状态的维护
159. 至多包含两个不同字符的最长子串	中等	上一题 $k=2$ 的特例，可用两个位置变量代替哈希表，与本题的滚动变量思路相通
1100. 长度为 K 的无重复字符子串	中等	定长窗口内判无重复，重点是窗口移动时频次的增减对称