【題解】CSES 2186 Special Substrings

#include <iostream>
#include <vector>
#include <map>
using namespace std;
 
int idx;
long long ans;
string s;
map <char, int> f;
map <vector<int>, int> mp;
 
int main() {
    cin >> s;
    for (int i = 0; i < s.length(); i++){
        if (!f.count(s[i])){
            f[s[i]] = idx;
            idx++;
        }
    }
    vector <int> tmp;
    for (int i = 0; i < idx; i++){
        tmp.push_back(0);
    }
    mp[tmp]++;
    int cnt = idx;
    for (int i = 0; i < s.length(); i++){
        if (tmp[f[s[i]]] == 0) cnt--;
        tmp[f[s[i]]]++;
        if (cnt == 0){
            for (int j = 0; j < idx; j++){
                tmp[j]--;
                if (tmp[j] == 0) cnt++;
            }
        }
        ans += mp[tmp];
        mp[tmp]++;
    }
    cout << ans << "\n";
}