题目描述

我们定义了一个函数 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 只包含大写英文字符。

算法

(思维题) $O(n)$

1. 预处理每个位置 i，左边第一个和自己一样字符的位置 left，右边第一个和自己一样字符的位置 right。该位置 i 贡献的答案就是 (i - left) * (right - i)。
2. 对每个位置进行统计。

时间复杂度

• 预处理的时间复杂度为 $O(n)$；每个位置常数时间统计，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要 $O(n)$ 的额外空间存储位置信息。

C++ 代码

class Solution {
public:
    #define LL long long
    int uniqueLetterString(string S) {
        const int mod = 1000000007;

        vector<int> last(26, -1);
        int n = S.length();

        vector<int> left(n, -1), right(n, n);

        for (int i = 0; i < n; i++) {
            left[i] = last[S[i] - 'A'];
            last[S[i] - 'A'] = i;
        }

        last = vector<int>(26, n);

        for (int i = n - 1; i >= 0; i--) {
            right[i] = last[S[i] - 'A'];
            last[S[i] - 'A'] = i;
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = (ans + (LL)(i - left[i]) * (right[i] - i)) % mod;

        return ans;
    }
};