统计子串中的唯一字符

难度: Hard

我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。

例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。

本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

示例 1：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2：

输入: s = "ABA"
输出: 8
解释: 除了 countUniqueChars("ABA") = 1 之外，其余与示例 1 相同。

示例 3：

输入：s = "LEETCODE"
输出：92

提示：

1 <= s.length <= 10⁵
s 只包含大写英文字符

Submission

运行时间: 142 ms

内存: 20.6 MB

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[c].append(i)
        ret = 0
        for arr in d.values():
            l = 0
            c = arr[0]
            arr.append(len(s))
            for r in arr[1:]:
                ret += (c - l + 1) * (r - c)
                l = c + 1
                c = r

        return ret

Explain

本题解使用了哈希表（字典）来统计字符串中每个字符的所有出现索引。对于每个字符，我们将字符在字符串中的所有索引存储在一个列表中，并额外在每个列表的末尾添加字符串长度作为边界。接着，针对每个字符的索引列表，计算每个字符在其每个出现位置的唯一性对于子字符串的贡献。具体方法是，对于列表中的每个索引，计算该索引与前一个索引之间的差值，并乘以该索引与下一个索引之间的差值。这样计算的结果即为该字符对所有子字符串中的唯一字符数的总贡献。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        d = defaultdict(list)
        # 构建每个字符的索引列表
        for i, c in enumerate(s):
            d[c].append(i)
        ret = 0
        # 计算每个字符的唯一性对子字符串的贡献
        for arr in d.values():
            l = 0
            c = arr[0]
            arr.append(len(s))
            for r in arr[1:]:
                ret += (c - l + 1) * (r - c)
                l = c + 1
                c = r

        return ret

Explore

在每个字符的索引列表末尾添加字符串长度作为边界，是为了方便计算字符串尾部字符对应的子字符串的数量。具体来说，对于字符串中的最后一个字符或任何字符的最后一个出现位置，我们需要一个边界值来标示从此位置到字符串结尾的子串范围。添加字符串长度作为边界，可以使得计算逻辑统一，避免在循环中进行特殊判断，简化了代码的复杂性。

在此计算公式中，`l`、`c`和`r`分别表示当前考虑的字符的前一个索引、当前索引和下一个索引。公式`(c - l + 1) * (r - c)`计算的是以当前字符`c`为唯一字符的所有可能的子字符串的数量。其中`(c - l + 1)`代表从位置`l+1`到位置`c`（包括c）之间的子串数量，`(r - c)`表示从位置`c`到位置`r-1`之间的子串数量。因此，乘积`(c - l + 1) * (r - c)`给出的是以当前位置字符为唯一字符的子字符串的总数。

在遍历字符串并构建字符的索引列表的过程中，我们使用一个哈希表（字典）来记录每个字符及其出现的所有索引。遍历字符串的每个字符时，我们查看该字符是否已经在字典中有对应的索引列表，如果有，则将当前的索引添加到该列表中；如果没有，则在字典中为这个字符创建一个新的列表，并添加当前索引。这样，每个字符的所有出现位置就会被顺序存储在列表中。通过这种方式，我们可以轻松处理字符的重复出现情况，并且能够快速访问任何字符的所有出现索引。