> For the complete documentation index, see [llms.txt](https://kseb0.gitbook.io/whiteboard/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kseb0.gitbook.io/whiteboard/arrays-and-strings/group-anagrams.md).

# Group Anagrams

Given an array of strings `strs`, group **the anagrams** together. You can return the answer in **any order**.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

**Example 1:**

```
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
```

**Approach1:**

We know that two string are anagrams if their sorted strings are equal.

* Iterate through the Strings of array
* We sort each String that we encounter in the loop and use it as Key
* Since the Keys consist of sorted Strings therefore all anagrams will share the same key.
* Essentially, when collision occurs (When two strings are anagram), we add that String to that it's respective place in the map. 
* Finally, we return the values of the HahsMap as it contained all the anagrams grouped in groups.

```java
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for(String s : strs){
            char[]a = s.toCharArray();
            Arrays.sort(a);
            String key = String.valueOf(a);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}
```

**`Time: O(mklogk)                Space: O(mk)`**

**Approach2: Optimal**

After completing our first-approach, we notice that we might be able to optimize our algorithm. Primarily due to the fact that we know that our Strings will only contain lower-case english letters. This subsequenly allows us to use **Counting Sort** which is an `O(N)` sorting algorithm in lieu of `Arrays.sort()` which is a `nlogn` algorithm (**quickSort**).

```java
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for(String s : strs){
            int[]freq = new int[26];
            for(int i = 0; i < s.length(); i++)
                freq[s.charAt(i) - 'a']++;
            String key = Arrays.toString(freq);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}
```

**`Time: O(mk)                Space: O(mk)`**

**Approach3: Brute-force**

When first presented with this problem, the below implementation is also an intuitive approach however the time complexity is exponential.

```java
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Set<List<String>> set = new HashSet<>();
        List<String> list = new ArrayList<>();
        
        for(int i = 0; i < strs.length; i++){
            char[]ch = strs[i].toCharArray();
            Arrays.sort(ch);
            for(int j = 0; j < strs.length; j++){
                char[]a = strs[j].toCharArray();
                Arrays.sort(a);
                if(Arrays.equals(ch, a)){
                    list.add(strs[j]);
                }
            }
            set.add(new ArrayList<>(list));
            list.clear();
        }
        return new ArrayList<>(set);
    }
}
```

**`Time: O(mklogk2)                Space: O(mk)`**