题解 | #abb#

// 假设abb序列 b的数量在序列中为cnt个

// 那么从cnt个字符任意选择两个 组合数为C(cnt,2)​=cnt∗(cnt−1)/2

#include<iostream>
using namespace std;

long long sum [100010][26];

int main(){
    int n;
    string s;
    cin >> n >> s;
  	// 后缀和数组 从右向左遍历 求对于每个字符后面有多少个不同的字母存在
    for(int i = n - 1; i >= 0; i --){
        for(int j = 0; j < 26; j ++){
            sum[i][j] = sum[i + 1][j];
        }
        sum[i][s[i] - 'a'] ++;
    }
    long long res = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < 26; j ++){
		  // 如果cnt = 1 组合数就为 0 所以不算在res里面 如果大于等于2就组合数
            if(j != s[i] - 'a')
                res += sum[i + 1][j] * (sum[i + 1][j] - 1) / 2;
        }
    }
    cout << res << endl;
    return 0;
}