Group Anagrams Together

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.

{ “abc”, “ged”, “dge”, “bac” } In the above example the array should be divided into 2 groups. The first group consists of { “abc”, “bac” } and the second group consists of { “ged”, “dge” }.

The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows. The first line of each test case contains a single integer ‘N’ denoting the number of strings. The next line contains 'N' single space-separated strings.

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.

1 <= T <= 5 1 <= N <= 1000 1 <= |STR_LIST[i]| <= 100 “STR_LIST[i]” contains only lowercase english letters. Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of strings, and |STR_LIST[i]| denotes the length of the i’th string. Time Limit: 1 sec.

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

Sorting based Approach

The idea behind this approach is that two or more than two strings are anagrams if and only if their sorted strings are equal. So we will use a HashMap, let’s say “anagramGroup”, where each key is a sorted string, and the key will be mapping to the list of indices from the given list of strings that form a group of anagrams. This means that if we sort the strings at those indices, we will get the sorted string that is the key for this list of indices in the hashmap.

The steps are as follows:

Define a HashMap, let’s say “anagramsGroups”. The key of the HashMap will be a string and the value will be an array/list of integers that will store the index numbers of the string corresponding to the key.
Iterate through the given strings, let’s say we are currently at index ‘i’.
1. Store the current string in a temporary variable, let’s say “temp”.
2. Sort the “temp” string and insert ‘i’ to the array corresponding to the “temp” string as the key of the HashMap.
Iterate through the HashMap and group all strings at indexes which belong to the same key of the HashMap.

Time Complexity

O(N * (|S| * log(|S|))), where ‘N’ is the number of strings and (|S|) is the maximum length of the given strings.

We are sorting each string which takes |S| * log(|S|) time and then inserting the string into the HashMap. Inserting and searching in a HashMap takes constant time. Thus, the total time complexity will be O(N * (|S| * log(|S|))).

Space Complexity

O(N * (|S|)), where ‘N’ is the number of strings and (|S|) is the maximum length of the given strings.

We are inserting each string into the HashMap after sorting. So in the worst case when there are no anagrams, the total number of strings in the HashMap will be N. Thus, the overall space complexity will be O(N * (|S|)).

Problem statement

Sample Input 1:

Sample Output 1 :

Explanation of the Sample Input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation of Sample Input 2 :