Submission #1540289

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1000000007;

int counts[30][200002];

int main(){
    string A;
    cin >> A;

    memset(counts, 0, sizeof(counts));
    int N = A.size();
    for(int i=0;i<26;i++){
        char c = 'a' + i;
        int v = 0;
        for(int j=N-1;j>=0;j--){
            counts[i][j] = v;
            if(A[j] == c){
                v++;
            }
        }
    }

    ll ans = 0;
    for(int i=0;i<N;i++){
        ans += N - 1 - i - counts[int(A[i] - 'a')][i];
    }
    cout << 1 + ans << endl;

    return 0;
}

Submission Info

Judge Result