Description

Submission

#include <bits/stdc++.h>

using namespace std;

// Complete the sherlockAndAnagrams function below.
int series_sum(int n, map<int, int>& dp) 
{
    auto iter = dp.find(n);
    if(iter != dp.end()) return iter->second;
    dp[n] = series_sum(n - 1, dp) + n;
    return dp[n];
}
int sherlockAndAnagrams(string s) {
    map<string, int> m;

    for(int i = 0; i < s.size(); ++i) {
        for(int j = i; j < s.size(); ++j) {
            string a = s.substr(i, j - i + 1);
            sort(a.begin(), a.end());
            auto it = m.find(a);
            if(it == m.end()) m.insert(make_pair(a, 1));
            else it->second++;
        }
    }
    int count = 0;
    map<int, int> dp;
    dp[0] = 0;
    for(auto iter: m) {
        count += series_sum(iter.second - 1, dp);
    }
    return count;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int q;
    cin >> q;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string s;
        getline(cin, s);

        int result = sherlockAndAnagrams(s);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}