Group Anagrams

PROBLEM STATEMENT

You have been given an array/list of strings 'inputStr'. You are supposed to return the strings as groups of anagrams such that strings belonging to a particular group are anagrams of one another.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase. We can generalize this in string processing by saying that an anagram of a string is another string with the same quantity of each character in it, in any order.

Note:

The order in which the groups and members of the groups are printed does not matter.

For example:

inputStr = {"eat","tea","tan","ate","nat","bat"}
Here {“tea”, “ate”,” eat”} and {“nat”, “tan”} are grouped as anagrams. Since there is no such string in “inputStr” which can be an anagram of “bat”, thus, “bat” will be the only member in its group.

Input Format :

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains an integer 'N' which denotes the number of strings.

The next line contains 'N' single space-separated strings. The strings consist of lower case English alphabets only.

Output Format:

For each test case/query, print the anagrams belonging to the same group in a single line, where all the anagrams are separated by a single space, and each group will be printed in a separate line.

The output for every test case will be printed in a separate line.

Note

You don't have to print anything. It has already been taken care of. Just implement the function.

Constraints :

1<= T <= 50
1<= N <= 100
1<= K <= 10

Where 'T' is the number of test cases, 'N' is the length of the given array/list of strings and ‘K’ is the maximum length of a string in the given array/list.

Time limit: 1 sec.

Approach 1

The key idea behind this approach is that we can transform each string into a string representing the character count. We will use an array “count”, of size 26 such that each element of the array represents the number of a’s, b’s, c’s and so on… We will be using these frequencies to create a string, delimited by ‘#’ characters, that we will use as a key for our HashMap.

For example :

str=”abbccc”, will be “#1#2#3#0#0#0#0…#0”, where there are 26 entries total with delimited by ‘#’.

Steps are as follows :

Make a HashMap let’s say anagramGroup, where the key of the string will be generated by transforming the array “count” into a string delimited by ‘#’ , and the key will be mapping to the list of indices from the given list of strings. The list of indices of each key will represent the indices of the strings which belong to the same group i.e. all the strings present at the indices of a particular list will be anagrams of one another
Iterate over given the list/array of strings. For each string in the list/array of strings:
- Store the frequency of character of the strings in the array count.
- Generate the key with the frequencies of characters, delimited by ‘#’. Let’s say “key”.
- Insert index of the current string into the HashMap corresponding to the “key”.
Once we are done with all the strings in the given list/array of the strings, the list of indices of each key will be representing all the indices of the strings which are anagrams to one another. So we will iterate through the value of our HashMap and group all the strings corresponding to the indices in the given array/list of strings for a particular key.

Try Problem