<p>Given an array of strings <code>strs</code>, group the <span data-keyword="anagram">anagrams</span> together. You can return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;eat&quot;,&quot;tea&quot;,&quot;tan&quot;,&quot;ate&quot;,&quot;nat&quot;,&quot;bat&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;bat&quot;],[&quot;nat&quot;,&quot;tan&quot;],[&quot;ate&quot;,&quot;eat&quot;,&quot;tea&quot;]]</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li>There is no string in strs that can be rearranged to form <code>&quot;bat&quot;</code>.</li>
	<li>The strings <code>&quot;nat&quot;</code> and <code>&quot;tan&quot;</code> are anagrams as they can be rearranged to form each other.</li>
	<li>The strings <code>&quot;ate&quot;</code>, <code>&quot;eat&quot;</code>, and <code>&quot;tea&quot;</code> are anagrams as they can be rearranged to form each other.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;&quot;]]</span></p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">strs = [&quot;a&quot;]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;a&quot;]]</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= strs.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= strs[i].length &lt;= 100</code></li>
	<li><code>strs[i]</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // std::unordered_map<string, vector<string>> wordMap;

        // for(string word: strs){
        //     string sortedWord = word;
        //     std::sort(sortedWord.begin(), sortedWord.end());
        //     if(wordMap.find(sortedWord) != wordMap.end()){
        //         wordMap[sortedWord].push_back(word);
        //     } else {
        //         wordMap[sortedWord] = {word};
        //     }
        // }

        // vector<vector<string>> result;
        // for(auto kv: wordMap){
        //     result.push_back(kv.second);
        // }

        // return result;



        int n = strs.size();
        vector<vector<string>> result;
        vector<array<int, 26>> intMapping;

        for(auto word: strs){
            array<int, 26>alphaArray = {};
            for(char character: word){
                alphaArray[character-'a']++;
            }
            intMapping.push_back(alphaArray);
        }

        std::unordered_map<std::array<int, 26>, vector<string>, ArrayHash> resGroupings;
        // std::unordered_map<string, vector<string>> resGroupings;

        // for(int i=0; i<n; i++){
        //     string key = "";
        //     for(auto alphaCount: intMapping[i]){
        //         key+="#";
        //         key += to_string(alphaCount);
        //     }
        //     resGroupings[key].push_back(strs[i]);
        // }

        for (int i = 0; i < n; i++) {
            resGroupings[intMapping[i]].push_back(strs[i]);
        }

        for(auto& grouping : resGroupings) {
            result.push_back(grouping.second);
        }


        return result;
    }
private:
    struct ArrayHash {
        std::size_t operator()(const std::array<int, 26>& arr) const {
            std::size_t hash_value = 0;
            std::hash<int> hash_fn;
            for (int val : arr) {
                hash_value ^= hash_fn(val) + 0x9e3779b9 + (hash_value << 6) + (hash_value >> 2);
            }
            return hash_value;
        }
    };
};
31040