题解 | #abb#

#include<iostream>
using namespace std;

int main(){
    int n;
    long sum=0;
    char str;
    
    //sub[c]：前一次字符c之前的字符串与当前字符c组成的abb个数
    //dp[1][c]：当前字符c之前的c字符个数
    //dp[0][c]：当前字符c之前与c不同的字符个数
    long dp[2][26]={0};
    long sub[26]={0};
    
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>str;
        int chr=str-'a';
        int nc=dp[1][chr]++;
        

        sub[chr]+=dp[0][chr];    //更新
        dp[0][chr]=i-nc;
        sum+=sub[chr];    //叠加
    }
    cout<<sum;
    return 0;
}

时间复杂度O(n),空间复杂度O(1)