思路

60pts

找出每一个字符前面最后一个与它相等的字符的下标 一点一点向前跳，答案累加上当前下标与扫到的下标之间元素的个数；

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s;
int f[N];
int main()
{
    memset(f,-1,sizeof f);
    cin>>s;
    map<char,int> mp;
    for(int i=0;i<s.size();i++)
    {   
        if(mp.count(s[i]))
        {
            f[i]=mp[s[i]];
        }
        mp[s[i]]=i;
    }
    long long  ans=0;
    for(int i=0;i<s.size();i++)
    {
        int j=i;
        while(f[j]>=0)
        {
            j=f[j];
            ans+=1ll*(i-j-1);
         }
    }
    cout<<ans<<endl;
}

发现会TLE最后四个测试点，原因是无法通过1e6的数据

100pts

同样思路使用前缀和优化即可

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
string s;
int f[N],f1[N];
signed main()
{
    cin>>s;
    map<char,int> mp,mp1;
    for(int i=0;i<s.size();i++)
    {
        if(mp.count(s[i]))
        {
            f[i]=mp[s[i]];
            f1[i]+=mp1[s[i]];
        }
        mp[s[i]]++;
        mp1[s[i]]+=i;
    }
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        int j=i;
		ans+=f[i]*(i-1)-f1[i];
    }
    cout<<ans<<endl;
}

`

`