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

这道题是给定一个字符串，求出其每个字串中拥有唯一字符的和，比如说一个字符串为"happy",它就有三个唯一字符，分别是"h","a","y"。这道题如果一个个枚举字符串的字串去计算肯定会超时，我们可以求出每个字符对最后答案的贡献，然后求和。假设一个字符的位置在i，那么首先先前找到与它相同的字符的位置j，再向后找到与它相同的字符的位置k，这个字符的贡献就是(i-j)(k-i)。可以这样想，假设一个字串是包含i的，那么在i之前共有(i-j)种选择，在i之后有(k-i)种选择，前面和后面的选择可以任意组合，因此位置i的字符是对这(i-j)(k-i)个字符串有贡献的，如果有重复的字符，那么这个字符就不会统计。如果是每次都从i开始向前向后找相同的字符串，时间复杂度最坏为O(n²),我优化了一下，用数组记录出每个字符出现过的位置，时间复杂度为O(n)。

class Solution {
public:
    int uniqueLetterString(string s) {
        int ans=0,c,pos;
        int sz=s.size();
        vector<int> v[26];
        int *vis=new int[sz+1];
        for(int i=0;i<26;i++)
        v[i].push_back(-1);
        for(int i=0;i<sz;i++)
        {
            c=s[i]-'A';
            v[c].push_back(i);
            vis[i]=v[c].size()-1;    
        }
        for(int i=0;i<26;i++)
        {
            v[i].push_back(sz);
        }
        for(int i=0;i<sz;i++)
        {
            c=s[i]-'A';
            pos=vis[i];
            ans+=(v[c][pos]-v[c][pos-1])*(v[c][pos+1]-v[c][pos]);
            ans%=1000000007;
        }
        return ans;
    }
};