Group Anagrams

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
35 upvotes
Asked in companies
IntuitExpedia GroupBNY Mellon

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
4
abab baba aabb abbc
5
aecd bcda acbd abdc acda
Sample Output 1 :
aabb abab baba
abbc
abdc acbd bcda
acda
aecd
Explanation of the Sample Input 1 :
In the first test case, in the first group ["aabb", "abab", "baba"], all the strings are anagrams of one another and in the second group ["abbc"] has no anagram, so it's the only member in its group.

In the second test case, in the first group ["abdc", "acbd", "bcda"] all the strings are anagrams of one another, and in second and third group, both ["acda"] and ["aecd"] have no anagram, so they are the only member in their group
Sample Input 2:
2
6
eat tea tan ate nat bat
5
cat dog tac god act
Sample Output 2 :
ate eat tea 
bat
nat tan
act cat tac
dog god
Explanation of the Sample Input 2 :
In the first test case, in the first group ["ate", "eat", "tea"] and the third group [“nat”, “tan”], all the strings are anagrams of one another and in the second group ["bat"] has no anagram, so it's the only member in its group and, 

In the second test case, in the first group ["act", "cat", "tac"] and in the second group ["dog", "god"], all the strings are anagrams of one another.
Hint

Can you use frequencies of characters in a string to find its anagrams?

Approaches (1)
Categorize by Count

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 :

  1. 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
  2. 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”.
  3. 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.
Time Complexity

O(N * K ), Where ‘N’ is the number of strings in the given array/list of strings, and ‘K’ is the maximum length of the string.

 

We are iterating through the given array/list of strings and for every string, we are storing the frequencies of characters which takes O(K) time. Also, generating the key for the HashMap takes constant time because there will be at most 26 distinct characters. Since there are ‘N’ strings in the given array/list, the overall time complexity will be O(N * K).

Space Complexity

O(N * K ), Where ‘N’ is the number of strings in the given array/list of strings, and ‘K’ is the maximum length of the string.

 

We are storing all the strings in the hashmap. Since there are ‘N’ strings and each string can have a maximum length of ‘K’, so the overall space complexity will be O(N * K).

Code Solution
(100% EXP penalty)
Group Anagrams
Full screen
Console