一开始想的是两次前缀和,发现自己蠢了
看了灵神的题解,类似于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;
}
};