题解 | #abb字串#

cnt[i] 表示在索引为0~i-1 之间小写字母出现的次数，i-cnt[i]表示除了这个字符以外其他字符的数量，这样我们就可以统计出像 ab这样的字符串有多少个 使用dp[i]记录 0~i-1 之间 以字符s[i]结尾的字符串有多少

#include<stdio.h>

int main()
{
    long long n,res=0;
    long long cnt[26]={0},dp[26]={0};
    scanf("%lld",&n);
    getchar();
    char *s=(char*)malloc(n+1);
    gets(s);
    
    for(int i=0;i<n;++i)
    {
        res+=dp[s[i]-'a'];
        dp[s[i]-'a']+=i-cnt[s[i]-'a'];
        ++cnt[s[i]-'a'];
    }
    
    printf("%lld",res);
    free(s);
    return 0;
}