abb

难度：3星

提示 1：对于每个字母 ch，找到后面和 ch 不等的两个相等字母的个数 cnt 即可，贡献为

$C_{cnt}^2=cnt\ast (cnt-1)\mathrm{/}2C\_\{cnt\}^2=cnt*(cnt-1)/2$

提示 2：快速得出每个 cnt 的方式：开一个后缀和数组 $sum[n][26]sum[n][26]$，$sum[i][j]sum[i][j]$ 代表 $jj$ 对应的字母，在坐标 $ii$ 到 $nn$ 出现的次数。这样就能 $O(1)O(1)$ 查询到每个字母后缀的出现次数。

#include<bits/stdc++.h>
using namespace std;
long long sum[101010][26];
int main(){
    int n,i,j;
    string s;
    cin>>n>>s;
    for(i=n-1;i>=0;i--){
        for(j=0;j<26;j++)sum[i][j]=sum[i+1][j];
        sum[i][s[i]-'a']++;
    }
    long long res=0;
    for(i=0;i<n;i++){
        for(j=0;j<26;j++){
            if(j!=s[i]-'a'){
                res+=sum[i+1][j]*(sum[i+1][j]-1)/2;
            }
        }
    }
    cout<<res;
}