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

1.题目描述

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

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

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

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

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

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

输入：s = “LEETCODE”
输出：92

提示：

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

2.思路分析

2.1 用变化量来思考

• 将所有子串按照其末尾字符的下标分组。
• 考虑两组相邻的子串：以 s[i-1]结尾的子串、以 s[i]结尾的子串。
• 以 s[i]结尾的子串，可以看成是以 s[i-1] 结尾的子串，在末尾添加上 s[i]组成。
• 从左往右遍历 s，考虑将 s[i] 添加到以 s[i-1] 结尾的子串的末尾。添加后，这些以 s[i-1] 结尾的子串的 countUniqueChars 值会如何变化？

以s=BCADEAFGA 为例，当遍历到最后一个 A 时：

• A 可以单独作为一个子串，其 countUniqueChars 值为 1；
• 往子串 G 和 FG 的末尾添加 A，由于 A 不在这些子串中，因此这些子串的 countUniqueChars 值都会增加 1；
• 往子串 AFG、EAFG 和 DEAFG 的末尾添加 A，由于 A 已经在这些子串中且恰好出现一次，添加后 A 重复出现，因此这些子串的 countUniqueChars 值都会减少 1；
• 往子串 ADEAFG、CADEAFG 和 BCADEAFG 的末尾添加 A，由于A 已经在这些子串中且不止出现一次，因此添加 A 不会改变这些子串的 countUniqueChars 值。

据此，我们在从左往右遍历 s 的同时，对每个字母 s[i] 记录其上一次出现的下标 ${\text{last}}_0[s[i]]$ 和上上一次出现的下标 ${\text{last}}_1[s[i]]$。通过上面的例子，我们可以算出从「以 s[i−1] 结尾的子串」到「以 s[i]] 结尾的子串」，countUniqueChars 值的和，增加/减少了多少：

• 增加了 $i-{\text{last}}_0[s[i]]$（注意 s[i] 单独作为一个子串，贡献了 1）；
• _减少了 ${\text{last}}_0[s[i]]-{\text{last}}_1[s[i]]$。

二者相加，总的变化量为: $i-2\cdot las{t}_0[s[i]]+las{t}_1[s[i]]$

特别地，如果 ${\text{last}}_0[s[i]]$或 ${\text{last}}_1[s[i]]$不存在，可以视作 −1，从而保证上式的正确性。

3.代码实现

3.1 用变化量来思考

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        result = total = 0
        last0, last1 = {}, {}
        for i, c in enumerate(s):
            total += i - 2 * last0.get(c, -1) + last1.get(c, -1)
            result += total
            last1[c] = last0.get(c, -1)
            last0[c] = i
        return result
1
2
3
4
5
6
7
8
9
10

复杂度分析
时间复杂度：O(n)，其中 n 为 s 的长度。
空间复杂度：$O(|\Sigma |)$，其中 $|\Sigma |$ 为字符集合的大小，本题中字符均为大写字母，所以 $|\Sigma |$=26。

参考:
1.https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/solution/by-muse-77-v7cs/
2.https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/solution/by-endlesscheng-ko4z/