题目描述：
对于一个字符串S ，我们定义S 的分值f (S ) 为S 中出现的不同的字符个数。
例如f (”aba”) = 2， f (”abc”) = 3, f (”aaa”) = 1。
现在给定一个字符串S [0 : n – 1]（长度为n），请你计算对于所有S 的非空子串S [i : j](0 ≤ i ≤ j < n)， f (S [i:: j]) 的和是多少。
输入格式：
输入一行包含一个由小写字母组成的字符串S 。
对于所有评测用例，1 ≤ n ≤ 100000。
输出格式
每组测试数据，输出一个字符串，为所求的答案。
输入样例
2
4
100
输出样例
bbaa
jihgfeeddccbbaa
思路：
笔者首先想到的是二维dp,这很好想，dp[i][j]代表f(s[i::j]),最后累加就行，但是这样的话时间复杂度就会达到O(n
2),看了一眼数据范围，10的五次方，所以要用dp的话肯定是一维dp,那么就想到dp[i]表示以i结尾的所有子串和，下面确定状态转移方程，首先思考dp[i]和dp[i-1]之间有什么关系，想到可以从0遍历到i,寻找最后一个与i值相等的元素的下标，但是这样子时间复杂度虽然达不到O(n
2),但是一不小心就有可能被卡掉，所以想到遍历整个字符串，预处理出每个位置的前面最靠近它的相等元素的下标。代码如下：
#include<iostream>
#include<cstring>
using namespace std;
string s;
long long kk[30];
long long pre[100005];
long long dp[100005];
long long ans=0;
int main(){
cin>>s;
int len=s.length();
memset(kk,-1,sizeof(kk));
memset(pre,-1,sizeof(pre));
for(int i=0;i<len;i++){
int tmp=s[i]-'a'+1;
pre[i]=kk[tmp];
kk[tmp]=i;
}
dp[0]=1;
for(int i=1;i<len;i++){
dp[i]=dp[i-1]+i-pre[i];
}
for(int i=0;i<len;i++){
ans+=dp[i];
}
cout<<ans<<endl;
return 0;
}