C++ One-pass 24ms 99.99% faster and 15.5 MB 99.73% less memory
The common idea is to use a hashmap (unordered_map) to group the strings. \nThere are several ways to choose the key for this task.\n\n1. Use sorted string as k
The common idea is to use a hashmap (unordered_map) to group the strings. \nThere are several ways to choose the key for this task.\n\n1. Use sorted string as key, e.g `eat` and `tea` produce the same key, `aet`.\n2. Use a counter array and transform it to a key somehow, e.g `none` and `neon` have 2 `n`s, 1 `o` and 1 `e`.\n3. Use a perfect (no collision) hash that produces a unique hash for each anagram.\n\nOption 1 is slow, because sorting takes time. Option 2 is better, but it takes more memory than necessary (`26 * sizeof(int)`), needs some transformation operation.\n\nFor Option 3, we could multiply each char, like `A` would become `1` and `Z` would become `26`. e.g `eat` -> `5 * 1 * 20` -> `100`, `tea` -> `20 * 5 * 1` -> `100`. Therefore, the hash is indifferent to the order of the chars.\n\nThe problem is these numbers are not primes, so their multiplication can cause collisions like `abebe` (not a word)-> `1 * 2 * 5 * 2 * 5` -> `100`. Actually since `A` is `1`, we can add infenitely many `A`s and still get the same hash!\n\nWe mentioned that these numbers were not primes, what we can do is instead of mapping `A...Z` to `1...26`, we can map each char to a different, preferably small primes. Thus, if we map each char to the first 26 primes, we can generate a unique hash for each anagram.\n\n\n```\nuint32_t hash(const string &word) {\n\tstatic int primes[26] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };\n\n\tuint32_t hash = 1;\n\tfor (char c : word) {\n\t\tint prime = primes[c - \'a\'];\n\t\thash *= prime;\n\t}\n\treturn hash;\n}\n```\n\n**EDIT: There is a bug in this hashing function, thanks to @WillF for pointing out the overflow issue, please refer to the comments for the updated one.**\n\nNow for the rest, normally you\'d see two passes for this task, one for grouping the strings and one for extracting all values of the `unorderd_map` like\n```\nunordered_map<uint32_t, vector<string>> mapping;\n...\nfor (string word : strs) { ... }\n\n// If only we could do `return mapping.values()`\nvector<vector<string>> result;\nfor (auto pair : mapping) {\n  result.push_back(pair.second);\n}\n\nreturn result;\n```\n\nThis has the problem of a lot of unnecessary copying. `unordered_map` is a blackbox, what we can do is to force it to sequentially place each group by taking care of the allocation process. The key remains the same, but the value now becomes a pointer to the actual container. This way we can directly return the required container without additional passes. \n\n```\nvector<vector<string>> groupAnagrams(vector<string>& strs) {\n\tunordered_map<uint32_t, vector<string> *> mapping;\n\tvector<vector<string>> ans;\n\n\t// Hack: \n\t//  If we reserve size beforehand, the vector will not grow \n\t//  during `push_back()` operations\n\t//  Thus, the pointers (vector<string> *) won\'t become invalidated, i.e dangling pointers\n\tans.reserve(strs.size());\n\n\t// Optional: \n\t//   Empirically, reserving 1/4th of the number of words \n\t//   gives the best performance\n\tmapping.reserve(strs.size() / 4);\n\n\tfor (string word : strs) {\n\t\tuint32_t h = hash(word);\n\n\t\tauto search = mapping.find(h);\n\t\tif (search == mapping.end()) {\n\t\t\t// Create a new bucket for this new anagram\n\t\t\tvector<string> v { word };\n\t\t\tans.push_back(std::move(v));\n\n\t\t\t// Note that we can\'t also do &v because it will soon get deallocated\n\t\t\tmapping[h] = &ans.back();\n\t\t} else {\n\t\t\tmapping[h]->push_back(word);\n\t\t}\n\t\t// This way we avoid copying the strings in the last step\n\t}\n\n\treturn ans;\n}\n```\n\nTo avoid the dangling pointer problem, instead of using references we can just store the index of the corresponding `vector<string>`, so if the `vector<vector<string>>` decides to grow, we will still access the correct container.\n(indexes and pointers are very related concepts after all.)\n\n```\nvector<vector<string>> groupAnagrams(vector<string>& strs) {\n    unordered_map<uint32_t, size_t> mapping;\n    vector<vector<string>> ans;\n    \n    // Optional: Not mandatory anymore, but still helps with performance\n    ans.reserve(strs.size());\n    \n    // Optional: \n    //   Empirically, reserving 1/4th of the number of words \n    //   gives the best performance\n    mapping.reserve(strs.size() / 4);\n    \n    for (string word : strs) {\n        uint32_t h = hash(word);\n        \n        auto search = mapping.find(h);\n        if (search == mapping.end()) {\n            // Create a new bucket for this new anagram\n            vector<string> v { word };\n            ans.push_back(std::move(v));\n            \n            // Store the corresponding vector index for this group\n            mapping[h] = ans.size() - 1;\n        } else {\n            size_t index = mapping[h];\n            ans[index].push_back(word);\n        }\n        // This way we avoid copying the strings in the last step\n    }\n    \n    return ans;\n}\n```
['C']