✅ 🔥 6 ms Runtime Beats 97.68% User🔥||  Code Idea ✅ ||  Algorithm & Solving Step  ✅ ||
\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### Problem Analysis :\n\nThe problem is to group strings that are anagrams of each 
![Screenshot 2024-12-08 at 8.55.19\u202FAM.png](https://assets.leetcode.com/users/images/7e8ae0a1-00a2-428d-bdcb-c481046c02f0_1733628349.0378728.png)\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### Problem Analysis :\n\nThe problem is to group strings that are anagrams of each other. An anagram is a word formed by rearranging the letters of another, using all the original letters exactly once.\n\n### Key Intuition :\n\nStrings that are anagrams of each other will have the same "signature" if sorted or represented by the frequency of their characters. By grouping strings based on their signature, we can efficiently identify and group anagrams.\n\n---\n\n### Approach 1: **Sorting as a Signature** :\n\n#### Idea:\n- Sort each string alphabetically. Anagrams will have the same sorted version.\n- Use a hashmap where the key is the sorted string, and the value is a list of anagrams.\n\n#### Algorithm:\n1. Initialize an empty hashmap.\n2. For each string in the array:\n   - Sort the string.\n   - Use the sorted string as a key in the hashmap and append the original string to the value list.\n3. Return all values in the hashmap as the result.\n\n#### Complexity:\n- **Time Complexity**: O(n . k log k), where n is the number of strings, and k is the average length of a string (sorting each string takes O(k log k).\n- **Space Complexity**: O(n.k), for the hashmap storage.\n\n#### Code:\n\n##### **C++**\n```cpp\n#include <vector>\n#include <string>\n#include <unordered_map>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<vector<string>> groupAnagrams(vector<string>& strs) {\n        unordered_map<string, vector<string>> anagramMap;\n\n        for (const string& str : strs) {\n            string sortedStr = str;\n            sort(sortedStr.begin(), sortedStr.end());\n            anagramMap[sortedStr].push_back(str);\n        }\n\n        vector<vector<string>> result;\n        for (const auto& entry : anagramMap) {\n            result.push_back(entry.second);\n        }\n        return result;\n    }\n};\n```\n\n##### **Java**\n```java\nimport java.util.*;\n\nclass Solution {\n    public List<List<String>> groupAnagrams(String[] strs) {\n        Map<String, List<String>> anagramMap = new HashMap<>();\n\n        for (String str : strs) {\n            char[] charArray = str.toCharArray();\n            Arrays.sort(charArray);\n            String sortedStr = new String(charArray);\n\n            anagramMap.putIfAbsent(sortedStr, new ArrayList<>());\n            anagramMap.get(sortedStr).add(str);\n        }\n\n        return new ArrayList<>(anagramMap.values());\n    }\n}\n```\n\n##### **Python**\n```python\nfrom collections import defaultdict\n\nclass Solution:\n    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:\n        anagram_map = defaultdict(list)\n\n        for s in strs:\n            sorted_str = \'\'.join(sorted(s))\n            anagram_map[sorted_str].append(s)\n\n        return list(anagram_map.values())\n```\n\n---\n\n### Approach 2: **Frequency Count as a Signature**\n\n#### Idea:\nInstead of sorting, use the frequency of each character (a 26-element array for lowercase English letters) as the signature. This avoids the overhead of sorting.\n\n#### Algorithm:\n1. Initialize an empty hashmap.\n2. For each string in the array:\n   - Compute a frequency count for the string.\n   - Use the frequency count (converted to a tuple) as a key in the hashmap and append the original string to the value list.\n3. Return all values in the hashmap as the result.\n\n#### Complexity:\n- **Time Complexity**: O(n . k), where nis the number of strings, and k is the average length of a string (building the frequency count takes O(k).\n- **Space Complexity**: O(n . k), for the hashmap storage.\n\n#### Code:\n\n##### **C++** :\n```cpp\n#include <vector>\n#include <string>\n#include <unordered_map>\n#include <array>\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<vector<string>> groupAnagrams(vector<string>& strs) {\n        unordered_map<string, vector<string>> anagramMap;\n\n        for (const string& str : strs) {\n            array<int, 26> charCount = {0};\n            for (char c : str) {\n                charCount[c - \'a\']++;\n            }\n            string key = "";\n            for (int count : charCount) {\n                key += "#" + to_string(count);\n            }\n            anagramMap[key].push_back(str);\n        }\n\n        vector<vector<string>> result;\n        for (const auto& entry : anagramMap) {\n            result.push_back(entry.second);\n        }\n        return result;\n    }\n};\n```\n\n##### **Java** :\n```java\nimport java.util.*;\n\nclass Solution {\n    public List<List<String>> groupAnagrams(String[] strs) {\n        Map<String, List<String>> anagramMap = new HashMap<>();\n\n        for (String str : strs) {\n            int[] charCount = new int[26];\n            for (char c : str.toCharArray()) {\n                charCount[c - \'a\']++;\n            }\n\n            StringBuilder keyBuilder = new StringBuilder();\n            for (int count : charCount) {\n                keyBuilder.append("#").append(count);\n            }\n            String key = keyBuilder.toString();\n\n            anagramMap.putIfAbsent(key, new ArrayList<>());\n            anagramMap.get(key).add(str);\n        }\n\n        return new ArrayList<>(anagramMap.values());\n    }\n}\n```\n\n##### **Python** :\n```python\nfrom collections import defaultdict\n\nclass Solution:\n    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:\n        anagram_map = defaultdict(list)\n\n        for s in strs:\n            char_count = [0] * 26\n            for char in s:\n                char_count[ord(char) - ord(\'a\')] += 1\n            anagram_map[tuple(char_count)].append(s)\n\n        return list(anagram_map.values())\n```\n\n---\n\n### Example Walkthrough :\n\n#### Input: `strs = ["eat","tea","tan","ate","nat","bat"]`\n\n#### **Sorting Approach**:\n1. After sorting:\n   - "eat" \u2192 "aet"\n   - "tea" \u2192 "aet"\n   - "tan" \u2192 "ant"\n   - "ate" \u2192 "aet"\n   - "nat" \u2192 "ant"\n   - "bat" \u2192 "abt"\n2. Grouping by sorted key:\n   - Key "aet" \u2192 ["eat", "tea", "ate"]\n   - Key "ant" \u2192 ["tan", "nat"]\n   - Key "abt" \u2192 ["bat"]\n\n#### **Frequency Count Approach**:\n1. Frequency counts:\n   - "eat" \u2192 [1, 0, 0, ..., 1, 1, 0]\n   - "tea" \u2192 [1, 0, 0, ..., 1, 1, 0]\n   - "tan" \u2192 [1, 0, ..., 1, 0, 0]\n   - "ate" \u2192 [1, 0, 0, ..., 1, 1, 0]\n   - "nat" \u2192 [1, 0, ..., 1, 0, 0]\n   - "bat" \u2192 [1, 1, ..., 0, 0, 0]\n2. Grouping by frequency key:\n   - Key [1, 0, ..., 1, 1, 0] \u2192 ["eat", "tea", "ate"]\n   - Key [1, 0, ..., 1, 0, 0] \u2192 ["tan", "nat"]\n   - Key [1, 1, ..., 0, 0, 0] \u2192 ["bat"]\n\n![image.png](https://assets.leetcode.com/users/images/a8b09c69-ba46-48ba-928e-dd83710190f7_1733628637.033828.png)\n
['Array', 'Hash Table', 'String', 'Sorting', 'C++', 'Java', 'Python3']