Group Anagrams

Problem

Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Examples

Example 1:

Input: strs = ["act","pots","tops","cat","stop","hat"]

Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Example 2:

Input: strs = ["x"]

Output: [["x"]]

Example 3:

Input: strs = [""]

Output: [[""]]

Constraints

• 1 <= strs.length <= 1000.
• 0 <= strs[i].length <= 100
• strs[i] is made up of lowercase English letters.

You should aim for a solution with O(m * n) time and O(m) space, where m is the number of strings and n is the length of the longest string.

Solution

For every string, count frequencies of each char, then add to a hash map.

class Solution {
    using AlphabetCounts = std::array<int, 26>;
    struct ArrayHasher {
        std::size_t operator()(const AlphabetCounts& a) const {
            std::size_t h = 0;
            for (auto e : a) {
                h ^= std::hash<int>{}(e)  + 0x9e3779b9 + (h << 6) + (h >> 2); 
            }
            return h;
        }   
    };
 
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // Use array of 26 counts (freq of each char in str) as key in map
        std::unordered_map<AlphabetCounts, std::vector<std::string>, ArrayHasher> freq_to_strs;
        for (auto &&str : strs) {
            AlphabetCounts ac{};
            // Count freq of each char
            for (const auto &c : str) {
                auto idx = static_cast<int>(c) - static_cast<int>('a');
                ++ac[static_cast<std::size_t>(idx)];
            }
            freq_to_strs[ac].push_back(std::move(str));
        }
 
        vector<vector<string>> result;
        for (auto &&[_, grouped_strs] : freq_to_strs) {
            result.push_back(std::move(grouped_strs));
        }
        return result;
    }
};