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

一开始想的是两次前缀和，发现自己蠢了

看了灵神的题解，类似于DP的思想

我们维护以每个字符串结尾的子字符串对答案的贡献，s[i]的贡献是多少？首先我们知道他需要自己单独一个串或者接在以s[i-1]结尾的那些字符串的后面，我们应当怎么操作？

我们发现那些以s[i-1]结尾的字符串可以分为三类：

记当前字符是c

1.出现过 c    1次

2.出现过 c    2次或者以上

3.没有出现过c

第一类接上c以后会让原来的那个答案-=1,第二类不影响，第三类+=1

所以我们只需要维护c上一次出现的位置，以及c上上次出现的位置就好了

然后你再用一下乘法原理  看看起点的种数就好了～～～～

class Solution {
public:
    int uniqueLetterString(string s) {
        int last0[100];
        int last1[100];
        memset(last0,-1,sizeof last0);
        memset(last1,-1,sizeof last1);


        int ans = 0,total=0;
        for(int i=0;i<s.size();i++){
            int t  = s[i]-'A';
            total += i+last1[t]-2*last0[t];
            ans+=total;
            last1[t] = last0[t];
            last0[t] = i;
        }

        return ans;

    }
};