由题可知 样例abcbcc被分为abb*1、acc*3、bcc*3、bcc*1。

不妨将问题简化为 求对于'a' 后面的相同的字符的个数，也就是前缀和。

例如 0位的'a' 后面有3个c、2个b，全排列次数为

c: 3*(3-1)/2 = 3

b: 2*(2-1)/2 = 1

所以acc*3、abb*1

建立长度26的数组arr，arr[i]表示字符i的出现次数，字符用 char值-'a' 后转int表示。

正向遍历O(n^2)：

从 首位开始 每一位都需要遍历一次后面的所有字符出现的次数。

如果 字符出现次数>=2并且字符非当前位字符，计算后加到结果里。

因为每一次都是在遍历后面的所有数字，近似冒泡排序效果，所以时间复杂度O(n^2)会超时。

反向遍历O(26n)：

从 末尾开始 每一次将当前字符出现次数+1。

同时以当前字符作为起始点，遍历26个字符出现次数，

如果 字符出现次数>=2并且字符非当前位字符，计算后加到结果里。

每一次计算仅遍历了26个字符的数组，与正向相比减少了遍历所有字符的操作。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long n,ans=0;
    string a;
    cin>>n>>a;
    vector<int> v(26,0);
    for(int i=n-1;i>=0;i--){
        int cur = a[i]-'a';
        v[cur]++;
        for(int j=0;j<26;++j){
            if(cur!=j&&v[j]>1) ans+=v[j]*(v[j]-1)/2;
        }
    }
    cout<<ans;
}