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

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 阿里
标签
字符串 哈希表 动态规划

题目描述

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

image-20260929104901276

image-20260929104901441

题意分析

字符串只含大写英文字母。对每个非空子串，统计其中恰好出现一次的字符个数，再将结果相加。“唯一”不是不同字符的种类数；内容相同但起止位置不同的子串也要分别计算。

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

核心思路

[!blue]

直接枚举所有子串会重复统计，换成问每次字符出现能为多少个子串贡献 1。固定位置 i，设同字符最近的前、后出现位置分别为 left、right。要让 s[i] 在子串中恰好出现一次，子串必须包含 i，同时不能包含这两个最近的同字符。

所以左端点可选 left + 1..i，共 i - left 种；右端点可选 i..right - 1，共 right - i 种。两端独立选择，贡献为 (i - left) * (right - i)。子串中每个被统计的唯一字符都对应其中唯一的一次出现，因此把所有位置贡献相加，恰好等于题目要求的总和。

从左到右扫描时，当前位置还不知道自己的后继，但已经能确定同字符上一次出现的后继。用 prev[c]、prevPrev[c] 记录字符 c 最近和次近的出现位置；新出现于 i 时，就为旧的 prev[c] 结算 (prev[c] - prevPrev[c]) * (i - prev[c])，再滚动更新这两个位置。

两个位置初始为 -1，使首次出现允许子串从下标 0 开始；尚未出现过的字符不结算。扫描结束后，每种字符只剩最后一次出现尚未结算，把它的后继设为 n，便允许右端点延伸到 n - 1。代码用宽整数乘法和累加，最后按题目保证的 32 位答案返回。

解题步骤

  1. 将每个字符的最近两次位置初始化为 -1。
  2. 遇到字符时，先结算其上一次出现的贡献。
  3. 将两次位置向前滚动。
  4. 扫描结束用 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+26)$，逐位置扫描并遍历固定字符集收尾。
  • 空间复杂度：$O(26)$，两组位置记录。

关键点总结

[!green]

  • 贡献属于一次出现，左右端点选择数相乘。
  • 先结算旧位置，再更新记录。
  • 没有下一次出现的字符需要统一收尾。
  • 每轮结束时，每种字符除了最近一次出现，其余出现的贡献都已结算。

易错点总结

[!yellow]

  • 将唯一理解为字符种类数：子串中出现多次的字符不能贡献 1。
  • 缺失位置用零初始化：漏掉允许从字符串开头开始的子串。
  • 先覆盖最近位置，再保存次近位置：两份记录变成同一位置。
  • 漏掉收尾：每个字符的最后一次出现都未计入。

相似题目

题目 难度 关联与区别
2262. 字符串的总引力 困难 原题按子串不同字符数计吸引力，本题只计恰出现一次的字符，位置贡献的边界不同。
907. 子数组的最小值之和 中等 同样从枚举所有子数组转为统计每个位置的贡献，本题边界由相同字符的前后出现位置决定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/22994786
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！