# Group Anagrams

An anagram is produced by rearranging the letters of first String into another String. Therefore, if `String t` is an anagram of `String s`, sorting both strings will result in two identical strings. Furthermore, if `s` and `t` have different lengths, `t` must not be an anagram of `s` and we can return early. Consider the following examples of anagram set:

```act, cat
tab, bat
tar, rat
star,rats```

The following method can be used to check if two Strings are an anagram or not.

```public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
```

Complexity analysis:

Time Complexity:  `Ο(nlogn)`. Assume that n is the length of s, sorting costs `Ο(nlogn) `and comparing two strings costs `O(n).` Sorting time dominates and the overall time complexity is `O(nlogn)`.

Space Complexity: `O(1)`. Space depends on the sorting implementation which, usually, costs `O(1)` auxiliary space if heapsort is used. Note that in Java, `toCharArray()` makes a copy of the string so it costs `O(n)` extra space, but we ignore this for complexity analysis as it is language-specific.

Now Given a set of random Strings, We need to write a function that groups all the anagrams together. This is an extension of identifying the anagrams. We can use `HashMap` to store the anagram group together. The algorithm is based on the logic: “sorting all anagrams will result in an identical String”. So, the key is the sorted word and the value is a list of words which sorts to an identical String. We will use the following data structure to store the anagram set:

`Map<String,List> anagramGroup = new HashMap<>();`

Where the key is the sorted result of a word and the value is the list of all anagrams.

1. Iterate over the `List/ Array` of words.
2. For each word convert the word into a character array. So if the word is “`cat`” then the array will be `[c,a,t]`.
3. Sort the array using `Arrays.sort(char[])`, so here the resulting sorted array will be `[a,c,t]`.
4. Again convert the array to String and check if there is any entry present for this key “`act`”.
5. If entry is present then add the original word “`cat`” in the List present in the value field.
6. Else create a new list and add the original word “`cat`” in the list and place the list in value filed against the sorted key.
7. Now if the word “`act`”/”`tac`” comes. Then the sorted key will be “`act`”. And we will find an entry for the key “`act`” and add both the word in the list.

Now let us check the Java implementation for the same:

```import java.util.*;

public class AnagramSet {

public static void main(String[] args) {
String[] StrArr = {"star", "dog", "car", "rats", "ars", "rca"};
List<List<String>>  anagramGroup= getAnagramSet(StrArr);
System.out.println(anagramGroup);
}

public static List<List<String>> getAnagramSet(String[] arr) {
List<List<String>> anagramGroup = new ArrayList<>();
if (arr == null || arr.length == 1) {
return anagramGroup;
}
Map<String, List<String>> anagramMap = new HashMap<>();
for (String word : arr) {
char[] charArray = word.toCharArray();
Arrays.sort(charArray);
String sorted = String.copyValueOf(charArray);
List<String> wordList = anagramMap.get(sorted);
if (wordList == null) {
wordList = new ArrayList<>();
anagramMap.put(sorted, wordList);
} else {
• Time Complexity: `O(NKlogK)`, where `N` is the length of `arr[]`, and K is the maximum length of a string in `arr`. The outer loop has complexity `O(N)` as we iterate through each string. Then, we sort each string in `O(KlogK)` time.
• Space Complexity: `O(NK)`, the total information content stored in `arr`