// C++ Code to group anagrams together by using frequency
// as keys
 
#include <bits/stdc++.h>
using namespace std;
 
const int MAX_CHAR = 26;
 
// function to generate hash of word s
string getHash(string &s) {
    string hash;
	vector<int> freq(MAX_CHAR, 0);
 
    // Count frequency of each character
    for(char ch: s)
        freq[ch - 'a'] += 1;
 
    // Append the frequency to construct the hash
    for(int i = 0; i < MAX_CHAR; i++) {
        hash.append(to_string(freq[i]));
    	hash.append("$");
    }
 
    return hash;
}
 
vector<vector<string>> anagrams(vector<string> &arr) {
    vector<vector<string>> res;
    unordered_map<string, int> mp;
    for (int i = 0; i < arr.size(); i++) {
        string key = getHash(arr[i]);
 
        // If key is not present in the hash map, add
        // an empty group (vector) in the result and
        // store the index of the group in hash map
        if (mp.find(key) == mp.end()) {
            mp[key] = res.size();
            res.push_back({});
        }
 
        // Insert the string in its correct group
        res[mp[key]].push_back(arr[i]);
    }
    return res;
}
 
int main() {
    vector<string> arr = {"act", "god", "cat", "dog", "tac"};
 
    vector<vector<string>> res = anagrams(arr);
    for(int i = 0; i < res.size(); i++) {
        for(int j = 0; j < res[i].size(); j++)
            cout << res[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Ly8gQysrIENvZGUgdG8gZ3JvdXAgYW5hZ3JhbXMgdG9nZXRoZXIgYnkgdXNpbmcgZnJlcXVlbmN5Ci8vIGFzIGtleXMKCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWF9DSEFSID0gMjY7CgovLyBmdW5jdGlvbiB0byBnZW5lcmF0ZSBoYXNoIG9mIHdvcmQgcwpzdHJpbmcgZ2V0SGFzaChzdHJpbmcgJnMpIHsKICAgIHN0cmluZyBoYXNoOwoJdmVjdG9yPGludD4gZnJlcShNQVhfQ0hBUiwgMCk7CiAgICAKICAgIC8vIENvdW50IGZyZXF1ZW5jeSBvZiBlYWNoIGNoYXJhY3RlcgogICAgZm9yKGNoYXIgY2g6IHMpCiAgICAgICAgZnJlcVtjaCAtICdhJ10gKz0gMTsKICAgIAogICAgLy8gQXBwZW5kIHRoZSBmcmVxdWVuY3kgdG8gY29uc3RydWN0IHRoZSBoYXNoCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgTUFYX0NIQVI7IGkrKykgewogICAgICAgIGhhc2guYXBwZW5kKHRvX3N0cmluZyhmcmVxW2ldKSk7CiAgICAJaGFzaC5hcHBlbmQoIiQiKTsKICAgIH0KICAgIAogICAgcmV0dXJuIGhhc2g7Cn0KCnZlY3Rvcjx2ZWN0b3I8c3RyaW5nPj4gYW5hZ3JhbXModmVjdG9yPHN0cmluZz4gJmFycikgewogICAgdmVjdG9yPHZlY3RvcjxzdHJpbmc+PiByZXM7CiAgICB1bm9yZGVyZWRfbWFwPHN0cmluZywgaW50PiBtcDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgYXJyLnNpemUoKTsgaSsrKSB7CiAgICAgICAgc3RyaW5nIGtleSA9IGdldEhhc2goYXJyW2ldKTsKICAgICAgCiAgICAgICAgLy8gSWYga2V5IGlzIG5vdCBwcmVzZW50IGluIHRoZSBoYXNoIG1hcCwgYWRkCiAgICAgICAgLy8gYW4gZW1wdHkgZ3JvdXAgKHZlY3RvcikgaW4gdGhlIHJlc3VsdCBhbmQKICAgICAgICAvLyBzdG9yZSB0aGUgaW5kZXggb2YgdGhlIGdyb3VwIGluIGhhc2ggbWFwCiAgICAgICAgaWYgKG1wLmZpbmQoa2V5KSA9PSBtcC5lbmQoKSkgewogICAgICAgICAgICBtcFtrZXldID0gcmVzLnNpemUoKTsKICAgICAgICAgICAgcmVzLnB1c2hfYmFjayh7fSk7CiAgICAgICAgfQogICAgICAKICAgICAgICAvLyBJbnNlcnQgdGhlIHN0cmluZyBpbiBpdHMgY29ycmVjdCBncm91cAogICAgICAgIHJlc1ttcFtrZXldXS5wdXNoX2JhY2soYXJyW2ldKTsKICAgIH0KICAgIHJldHVybiByZXM7Cn0KCmludCBtYWluKCkgewogICAgdmVjdG9yPHN0cmluZz4gYXJyID0geyJhY3QiLCAiZ29kIiwgImNhdCIsICJkb2ciLCAidGFjIn07CiAgICAKICAgIHZlY3Rvcjx2ZWN0b3I8c3RyaW5nPj4gcmVzID0gYW5hZ3JhbXMoYXJyKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCByZXMuc2l6ZSgpOyBpKyspIHsKICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgcmVzW2ldLnNpemUoKTsgaisrKQogICAgICAgICAgICBjb3V0IDw8IHJlc1tpXVtqXSA8PCAiICI7CiAgICAgICAgY291dCA8PCAiXG4iOwogICAgfQogICAgcmV0dXJuIDA7Cn0=