题解 | #abb#

//
// Created by good boy on 2023/12/29.
//

/**题意描述
小聪最近爱上了 abb 型语句，比如“叠词词”、“恶心心”
拿到了一个只含有小写字母的字符串，想知道有多少个 "abb" 型的子序列？

 定义： abb 型字符串满足以下条件：
字符串长度为 3 。
字符串后两位相同。
字符串前两位不同。
*/

/** 思路描述
 *  1. 统计字符串中a-z每个字符出现的次数
 *  2.枚举abb中的a，每枚举一位就减去当前位置上的字符数量，
 *    这样cnt【】字符数组就是当前位置往后字符出现的次数
 *  3. 枚举abb中的bb，通过组合数的形式枚举即可C（n，2）;
 */

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int cnt[26];
long long res;
long long Cn2(int n){
    long long ans = n*(n-1)/2;
    return ans;
}

int main(){
    int n;cin>>n;
    string s;cin>>s;
    for(int i=0;i<n;i++)
        cnt[s[i]-'a']++;
    for(int i=0;i<n;i++){
        char c = s[i];
        cnt[s[i]-'a']--;
        for(int j=0;j<26;j++){
            if(c-'a' == j)continue;
            if(cnt[j]>=2)
                res += Cn2(cnt[j]);
        }
    }
    cout<<res<<endl;

    return 0;
}