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

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

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

解析：

• 首先，解释一下唯一,t=“LEEA”,那么唯一字符串就是两个 L A
• 说到子字符串（连续），就可以枚举每个字母作为子字符串的结尾，然后利用动态规划解决
• 然后，再看一下子字符串的之间有什么关系：s=“LEEAE”:
• 以L结尾：L
• 以E结尾：E EL
• 以E结尾：E EE EEL
• 以A结尾：A AE AEE AEEL
• 以E结尾：E EA EAE EAEE EAEEL
• 可以发现，后一个字母结尾的子字符串，相当于在前一个字母结尾的子字符串上添加上结尾字母所组成。A、 AE 、AEE、 AEEL 加上最后一个E（值为a），就变成了E、 EA 、EAE 、EAEE 、EAEEL(唯一字符值记为b)。那他们之间的唯一字母有什么关系呢？
• 如果不考虑重复，他们之间的关系就是b=a+5,5就相当于最后一个E在五个字符串中贡献的值。
• 但是对于重复应该怎么解决呢？重复之后不仅不会贡献值，反而会将原来相同字母贡献的值给减去。例如：E、 EA 、EAE 、EAEE 、EAEEL。新加的E只有在E、EA中贡献值，但是在EAE 、EAEE 、EAEEL中相当于将原来的E贡献值给消去了。因此，b = a+2-3,(为什么取2呢，是因为s=“LEEAE”，最后一个E仅仅对E、EA有所贡献，前边3个相当于减去E的贡献)。
• 还有个问题就是重复减去？s=“LEEAE”: 最后一个E作为结尾时，E、 EA 、EAE 、EAEE 、EAEEL。在AEE 、AEEL添加E并不会对贡献值削弱，因为本身已经存在了EE，前边计算唯一字符个数时已经将E抛弃了，后续添加E也不会对结果产生影响。因此，b=a+2-3+2(最后一个2相当于重复减的量);

代码：

class Solution {
public:
    int uniqueLetterString(string s) {
        int res=0,pre=0;
        int n=s.size();
        // 分别记录倒数第二个相同字母位置
        // 倒数第三个相同字母位置
        int idx[26],idx2[26];
        // 赋值为-1，方便计算元素个数
        memset(idx,-1,sizeof(idx));
        memset(idx2,-1,sizeof(idx2));
        for(int i=0;i<n;i++){
        	// pre为前一个字母为结尾的字符数+新字母作为结尾贡献的值
            pre+=i-idx[s[i]-'A'];
            // 说明前边已经出现该字母
            if(idx[s[i]-'A']!=-1)
            	// 减去的值
                pre-=idx[s[i]-'A']+1;
            // 将重复减去的值加回来
            // LEEAE ，最后一个E应该贡献2，减去3，但是遇到第二个E时，
            // 已经将E,EL中贡献的E减去了相当于重复减去，需要把重复减去的加回来
            if(idx2[s[i]-'A']!=-1)
                pre+=idx2[s[i]-'A']+1;
            res+=pre;
            idx2[s[i]-'A']= idx[s[i]-'A'];
            idx[s[i]-'A']=i;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30