题解 | #abb#

//从后向前遍历字符串
//dp表示当前字符之前能配对的总个数
//dp[i+1] = dp[i] + sum
//其中，sum就是当前这个字符能配对abb的个数
//sum = C_n_2 
//path记录了26个字母重复的次数，随着i而更新
//需要注意的是int会溢出，所以用long long
#include <iostream>
#include <vector>
using namespace std;
long long cn2(int n){
    long long a22 = 2, an2 = n*(n-1);
    return an2/a22; 
}

int main() {
    int n;
    cin>>n;
    string str;
    cin>>str;
    if(n<3){
        cout<<0;
        return 0;
    }
    vector<long long> path(26,0);//代表的是第i个下标后各字母的数量，从后向前
    vector<long long> dp(n+1,0);//从后向前到达第i个下标时，abb型字符串的数目
    int start = str.size()-1;
    for(int i=0;i<str.size();++i){
        int c = str[start-i] - 97;
        //cout<<str[start-i]<<endl;
        long long sum = 0;
        for(int j=0;j<26;++j){
            if(j!=c)sum = sum + cn2(path[j]);
        }
        //cout<<sum<<endl;
        dp[i+1] = dp[i] + sum;
        ++path[c];
    }
    cout<<dp[n];
    return 0;
}
// 64 位输出请用 printf("%lld")