算法1
(dp) $O(n)$
//思路:贡献法,对于dp[i-1]的每一个子串,dp[i]的每一个子串即为dp[i-1]中的每一个子串末尾加上str[i]
//所以可以状态转移,二者相差的值即为str[i]产生的贡献
//(1)对于以j1+1~i开头,所有以i结尾的子串,str[i]只出现了一次,对于每个子串都会有1个新的贡献,共i-j1个子串,所以
//这部分会增加i-j1点贡献
//(2)对于以j2+1~j1开头,所有以i结尾的子串,由于str[i]在之前已经出现过一次,会有1个贡献,现在
//str[i]又出现了一次,就会导致这个字符的贡献消失,从而每个子串的贡献减少1,所以这部分会减少j1-j2个贡献
//(3)对于以1~j2开头,所有以i结尾的子串,由于str[i]在之前出现的数量已经超过一次,本身这个字符就没有贡献
//所以再增加一个str[i]也不会产生新的贡献。所以这部分没有贡献
//故状态转移方程为:dp[i]=dp[i-1]+(i-j1)-(j1-j2)
C++ 代码
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
string str;
int dp[100010];//dp[i]表示考虑前i个字符,且必须以第i个字符结尾的所有子串的f的和
//ans=dp[1]+dp[2]+……+dp[n]
//状态表示:设第i个字符之前的最后一个与str[i]相同的字符的位置为j1,
//倒数第二个与str[i]相同的字符的位置为j2,则:dp[i]=dp[i-1]+(i-j1)-(j1-j2)
map<char,int> mp1;//mp1['ch']=k表示当枚举到第i个字符,str[i]在i之前出现的最后一个位置是k
map<char,int> mp2;//mp2['ch']=k表示当枚举到第i个字符,str[i]在i之前出现的倒数第二个位置是k
int main()
{
cin>>str;
int n=str.size();
str='?'+str;
dp[1]=1;
mp1[str[1]]=1;
mp2[str[1]]=0;
for(int i=2;i<=n;i++)
{
int j1=mp1[str[i]];
int j2=mp2[str[i]];
dp[i]=dp[i-1]+(i-j1)-(j1-j2);
mp2[str[i]]=mp1[str[i]];//倒数第二个字符变为原来的倒数第一个字符
mp1[str[i]]=i;//当前位置变为倒数第一个字符的位置
}
long long res=0;
for(int i=1;i<=n;i++) res+=dp[i];
cout<<res;
return 0;
}