题解 | #abb#

#include <iostream>
using namespace std;
typedef long long int ll;
string s;
ll n;
ll ret = 0;
const int N = 1e5 + 10;
ll dp[N];
ll f[N];
ll g[N];
int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        int x = s[i] - 'a'; 
        dp[i] = f[x];//dp[i]表示以i位置为结尾的序列有多少个_xx；
        ret += dp[i];// f[x] 更新前  [0,i-1]中有多少个_x；
        f[x] = f[x] + i - g[x];//更新后[0,i]中有多少个_x
        g[x] += 1;//g[x]更新前[0,i-1]区间里有多少个x， 那么就有i-g[x]个非x的；
    }
    cout << ret;
    return 0;
}