乘法原理 LeetCode 828. 统计子串中的唯一字符

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

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

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

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

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

需要统计所有子串中唯一字符次数的总和，可以换个角度统计每个字符在不同子串中出现的次数。

假设当前字符为s[i],s[i]出现的子串只能出现一次s[i]，如果出现两次那么s[i]就不计算。所以如果想要计算s[i]对结果的贡献，需要找出左边第一次出现s[i]的地方L，和右边第一次出现s[i]的地方R。

所以只包含一次s[i]的字符串 左边界必须大于等于L+1，右边界必须小于等于R-1，左边界可以取L+1~i ,右边界可以取i到R-1，所以一共有（i-L）*(R-i-2)种情况。

因为都是大写字母，可以使用L(i),R(i)数组表示i左边第一次出现s[i]的下标，i右边第一次出现s[i]的下标。

可以在遍历时使用一个大小为26的数组维护所有字母最后一次出现的下标，然后更新L(i)和R(i)。

class Solution {
public:
    int uniqueLetterString(string s) {
       int n = s.size();
       vector<int>l(n),r(n);
       vector<int>p(26,-1);
       for(int i=0;i<n;i++){
           l[i]=p[s[i]-'A'];
           p[s[i]-'A']=i;
       }
       p=vector<int>(26,n);
       for(int i=n-1;i>=0;i--){
           r[i]=p[s[i]-'A'];
           p[s[i]-'A']=i;
       }
       int res=0,MOD=1e9+7;
       for(int i=0;i<n;i++){
           res = (res+(long long)(i-l[i])*(r[i]-i))%MOD;
       }
       return res;
    }
};