4 approaches||Freq count/sort->compression||12ms Beats 99.82%
Intuition\n Describe your first thoughts on how to solve this problem. \nSeveral kinds of solutions.\n\n__Theorem. s is an anagram of t \u2005\u27FA freq(s)=fre
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSeveral kinds of solutions.\n\n__Theorem. s is an anagram of t \u2005\u27FA freq(s)=freq(t) \u2005\u27FA sorted(s)=sorted(t) \u27FA sorted(g(s))=sorted(g(t)) where g is a compression function\nIn other words, s is a permutation of t.__\n\nTo solve this problem, hash table is a must.\n1 is very easy solution. Since strings are anagrams being same string after sorting, using sorted as the key for hash table (`unordered_map<string, vector<int>>`). this solution has elapesed time 12ms Beats 99.82%. Its similar python version is also provided.\n\nOne Leetcode hard problem related to anagram counting is solved in the very different way:\n[2514. Count Anagrams](https://leetcode.com/problems/count-anagrams/solutions/4685207/c-euclidean-algorithm-modular-inverse-factorials-12ms-beats-100/)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn English subtitles if necessary]\n[https://youtu.be/WjrWkPysfRM?si=OPTBMyoRLLXkAM7T](https://youtu.be/WjrWkPysfRM?si=OPTBMyoRLLXkAM7T)\nThe 1st way is easy & fast, and is recomended for all.\n\n2nd one is a little boring. First use freq count, then use hash table (`map<vector<int>, vector<int>>`) which is slow.\n\n3rd C++ solution uses own hash (very easy one) & use freq count, then use hash table `unordered_map<array<uint8_t, 26>, vector<int>, MyHash> freq2idx` which runs in 14ms beats 99.64%.(This is revised thanks to @Sergei for the comments)\n\n4th C++ solution uses freq count,& then convert it into a compressed sorted string. Using this compressed string as the key for  the hash table. This method is  suitable for very long strings  which has elapsed time 19ms & beats 97.13%!\n\nIf you are insist using `unordered_map<vector<K>, vector<int>. ownHash>`, which is possible only when you\'ve built your own hash `ownHash` function for `vector<K>` & could be fast or slow depending on implementation.\n\n|Method| elapsed time| Time record | Space |\n|---|---|---|---|\n|C++ String sort+unordered_map|12ms|99.82%|22.45MB|\n|C++ Freq count+map|38ms|30.59%|28.82MB|\n|C++ Freq count+revised own hash+ unordered_map|14ms|99.64%|22.30MB|\n|C++ Freq count+ compressed sorted string+ unordered_map|19ms|97.13%|23.30MB|\n|Python String sort+ dict|80ms|93.38%|20.03MB|\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1: $$O(nm\\log(m))$$ where m=max(len(s))\n2: $$O(nm\\log n)$$\n3: $$O(nm)$$\n4: $$O(nm)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(nm)$$\n\n# Codes String sort+hash table||C++ 12ms Beats 99.82%\n\n```C++ []\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    unordered_map<string, vector<int>> mp;\n    vector<vector<string>> groupAnagrams(vector<string>& strs) {\n        int n=strs.size();\n        for(int i=0; i<n; i++){\n            string f=strs[i];\n            //strings are anagrams <=> same string after sorting\n            sort(f.begin(), f.end());\n            if (mp.count(f)==0) mp[f]={i};\n            else mp[f].push_back(i);\n        }\n        vector<vector<string>> ans(mp.size());\n        int i=0; \n        for(auto& [key, v] : mp){\n            for(int x: v)\n                ans[i].push_back(strs[x]); \n            i++;\n        }  \n        return move(ans);\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n```python []\nclass Solution:\n    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n        #anagram strings are after sorting the same \n        mp ={}\n        #for i, s in enumerate(strs):\n        for s in strs:\n            f=str(sorted(s))\n            if f not in mp:\n                mp[f]=[]\n            mp[f].append(s)\n        return list(mp.values())\n        \n```\n\n# C++ using map\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    vector<int> freq(string& s){\n        vector<int> alphabet(26, 0);\n        for (char c: s){\n            alphabet[c-\'a\']++;\n        }\n        return alphabet;\n    }\n    map<vector<int>, vector<int>> freq2idx;\n    vector<vector<string>> groupAnagrams(vector<string>& strs) {\n        int n=strs.size();\n        for(int i=0; i<n; i++){\n            vector<int> f=freq(strs[i]);\n            if (freq2idx.count(f)==0) freq2idx[f]={i};\n            else freq2idx[f].push_back(i);\n        }\n        vector<vector<string>> ans(freq2idx.size());\n        int i=0; \n        for(auto& [key, v] : freq2idx){\n            for(int x: v)\n                ans[i].push_back(strs[x]); \n            i++;\n        }  \n        return move(ans);\n    }\n};\n\n```\n\n# C++ using revised own hash & unordered_map||14ms Beats 99.64%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nstruct MyHash {\n    size_t operator()(array<uint8_t, 26> const& v) const {\n        size_t h = 0;\n        for (auto x: v) {\n            h^=(x+0x9e3779b9+(h<<6)+(h>>2));\n        }\n        return h;\n    }\n};\nclass Solution {\npublic:\n    array<uint8_t, 26> freq(string& s){\n        array<uint8_t, 26> alphabet;\n        alphabet.fill(0);\n        for (char c: s){\n            alphabet[c-\'a\']++;\n        }\n        return alphabet;\n    }\n    unordered_map<array<uint8_t, 26>, vector<int>, MyHash> freq2idx;\n    vector<vector<string>> groupAnagrams(vector<string>& strs) {\n        int n=strs.size();\n        for(int i=0; i<n; i++){\n            array<uint8_t, 26> f=freq(strs[i]);\n            if (freq2idx.count(f)==0) freq2idx[f]={i};\n            else freq2idx[f].push_back(i);\n        }\n        vector<vector<string>> ans(freq2idx.size());\n        int i=0; \n        for(auto& [key, v] : freq2idx){\n            for(int x: v)\n                ans[i].push_back(strs[x]); \n            i++;\n        }  \n        return move(ans);\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ using compressed sorted string & unordered_map\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    string freq(string& s){\n        int alphabet[26]={0};\n        for (char c: s){\n            alphabet[c-\'a\']++;\n        }\n        string ans="";\n        for (int i=0; i<26; i++){\n            int x=alphabet[i];\n            if (x==0) continue;\n            ans.push_back(\'a\'+i);\n            if (x>1) ans+=to_string(x);//a compressed form\n        }\n        return ans;\n    }\n    unordered_map<string, vector<int>> freq2idx;\n    vector<vector<string>> groupAnagrams(vector<string>& strs) {\n        int n=strs.size();\n        for(int i=0; i<n; i++){\n            string f=freq(strs[i]);\n            if (freq2idx.count(f)==0) freq2idx[f]={i};\n            else freq2idx[f].push_back(i);\n        }\n        vector<vector<string>> ans(freq2idx.size());\n        int i=0; \n        for(auto& [key, v] : freq2idx){\n            for(int x: v)\n                ans[i].push_back(strs[x]); \n            i++;\n        }  \n        return move(ans);\n    }\n};\n\n```\n
['Hash Table', 'Sorting', 'C++', 'Python3']