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

Note :

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.

Example:

{ “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” }.

Input Format:

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.

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 need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Group Anagrams Together

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

Note :

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.

Example:

{ “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” }.

Input Format:

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.

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 need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

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.

Accepted Answer

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.

Space Complexity: OtherExplanation:

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|)).

Time Complexity: OtherExplanation:

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|))).

C++ (g++ 5.4)

/*

    Time Complexity: 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.

*/



#include 

#include 



vector> groupAnagramsTogether(vector &strList)

{

    // HashMap for storing anagrams.

    unordered_map> anagramGroups;



    int n = strList.size();



    // Iterate through the strings.

    for (int i = 0; i < n; i++)

    {



        string temp = strList[i];



        // Sort the temporary string.

        sort(temp.begin(), temp.end());



        // Insert the sorted string into the HashMap.

        anagramGroups[temp].push_back(i);

    }



    int totalGroups = anagramGroups.size();

    

    // For storing the groups.

    vector> groups(totalGroups);



    int groupNumber = 0;



    // Iterate through the HashMap.

    for (unordered_map>::iterator i = anagramGroups.begin(); i != anagramGroups.end(); i++)

    {

        // Insert all strings of the key into one group.

        for (int j : i->second)

        {

            groups[groupNumber].push_back(strList[j]);

        }



        groupNumber++;

    }



    return groups;

}

Python (3.5)

'''

    Time Complexity: 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.

'''



from collections import defaultdict



def groupAnagramsTogether(strList):

    

    groupedWords = defaultdict(list)

 

    # Put all anagrams together in a dictionary, where key is sorted word.

    for word in strList:

        groupedWords["".join(sorted(word))].append(word)

        

    result = []

    

    # Put all anagrams together in the result array.

    for key in groupedWords:

        result.append(groupedWords[key])

        

    return result

Java (SE 1.8)

/*

    Time Complexity: 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.

*/



import java.util.Arrays;

import java.util.HashMap;

import java.util.ArrayList;

import java.util.Collections;



public class Solution {

    public static ArrayList> groupAnagramsTogether(ArrayList strList) {

        // HashMap for storing anagrams.

        HashMap> anagramGroups = new HashMap>();



        int n = strList.size();



        // Iterate through the strings.

        for (int i = 0; i < n; i++) {



            // Sort the temporary string.

            char[] chars = strList.get(i).toCharArray();

            Arrays.sort(chars);

            String temp = new String(chars);



            // Insert the sorted string into the HashMap.



            ArrayList arr = anagramGroups.get(temp);

            if (arr == null) {

                arr = new ArrayList();

            }

            arr.add(i);

            anagramGroups.put(temp, arr);

        }



        int totalGroups = anagramGroups.size();



        // For storing the groups.

        ArrayList> groups = new ArrayList>(totalGroups);



        for (int i = 0; i < totalGroups; i++) {

            groups.add(new ArrayList());

        }



        int groupNumber = 0;



        // Iterate through the HashMap.

        for (HashMap.Entry> i : anagramGroups.entrySet()) {

            // Insert all strings of the key into one group.

            for (int j : i.getValue()) {

                groups.get(groupNumber).add(strList.get(j));

            }

            groupNumber++;

        }



        return groups;

    }

}

Accepted Answer

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 “frequency", 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 “anagramGroups” where the key of the string will be generated by transforming the array “frequency” 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:
1. Store the frequency of character of the strings in the array “frequency”.
2. Generate the key with the frequencies of characters, delimited by ‘#’. Let’s say “key”.
3. 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.

Space Complexity: OtherExplanation:

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. 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|)).

Time Complexity: OtherExplanation:

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

We are iterating through each string which takes |S| time to calculate the frequency of each character and then we are generating the key for the HashMap which will take constant time. Then we are inserting the key into the HashMap. Inserting and searching in a HashMap takes constant time. Thus, the total time complexity will be O(N * (|S|)).

Python (3.5)

'''

    Time Complexity: O(N * (|S|)))

    Space Complexity: O(N * (|S|))



    Where 'N' is the number of Strings, 

    and (|S|) is the maximum length of the given Strings.

'''



from collections import defaultdict



def groupAnagramsTogether(strList):

    groupedWords = defaultdict(list)

 

    # Put all anagram words together in a dictionary, where key is frequency string.

    for word in strList:

        frequency = [0] * 26

        

        for character in word:

            frequency[ord(character) - 97] += 1

        

        key = ""

        

        # Calculating the key. 

        for i in frequency:

            key = key + "#" + str(i)

            

        groupedWords[key].append(word)

        

    result = []

    

    # Putting all anagrams ina result array.

    for key in groupedWords:

        result.append(groupedWords[key])

        

    return result

C++ (g++ 5.4)

/*

    Time Complexity: O(N * (|S|)))

    Space Complexity: O(N * (|S|))



    Where 'N' is the number of strings,

    and (|S|) is the maximum length of the given strings.

*/



#include 

#include 



vector> groupAnagramsTogether(vector &strList)

{

    // HashMap for mapping group of anagrams.

    unordered_map> anagramGroups;



    int n = strList.size();



    // Iterate through the given strings.

    for (int i = 0; i < n; i++)

    {

        // Calculate the frequency of the characters of the string.

        vector frequency(26, 0);



        for (char j : strList[i])

        {

            frequency[j - 'a']++;

        }

        string key = "";



        // Generate the key for the current string.

        for (int j = 0; j < 26; j++)

        {

            key.push_back('#');

            key.append(to_string(frequency[j]));

        }



        // Insert the string into the HashMap.

        anagramGroups[key].push_back(i);

    }



    int totalGroups = anagramGroups.size();



    // For storing groups of anagrams.

    vector> groups(totalGroups);



    int groupNumber = 0;



    // Iterate through the HashMap.

    for (unordered_map>::iterator i = anagramGroups.begin(); i != anagramGroups.end(); i++)

    {

        // Insert all strings of the key into one group.

        for (int j : i->second)

        {

            groups[groupNumber].push_back(strList[j]);

        }



        groupNumber++;

    }



    return groups;

}

Java (SE 1.8)

/*

    Time Complexity: O(N * (|S|)))

    Space Complexity: O(N * (|S|))



    Where 'N' is the number of Strings,

	and (|S|) is the maximum length of the given Strings.

*/



import java.util.ArrayList;

import java.util.HashMap;



public class Solution {

    public static ArrayList> groupAnagramsTogether(ArrayList strList) {

        // HashMap for mapping group of anagrams.

        HashMap> anagramGroups = new HashMap>();



        int n = strList.size();



        // Iterate through the given Strings.

        for (int i = 0; i < n; i++) {

            // Calculate the frequency of the characters of the String.

            ArrayList frequency = new ArrayList(26);



            for (int j = 0; j < 26; j++) {

                frequency.add(0);

            }



            for (char j : strList.get(i).toCharArray()) {

                frequency.set(j - 'a', frequency.get(j - 'a') + 1);

            }

            StringBuilder key = new StringBuilder();



            // Generate the key for the current String.

            for (int j = 0; j < 26; j++) {

                key.append("#"+frequency.get(j));

            }



            // Insert the String into the HashMap.

            ArrayList arr = anagramGroups.get(key.toString());

            

            if(arr == null){

                arr = new ArrayList();

            }



            arr.add(i);



            anagramGroups.put(key.toString(), arr);

        }



        int totalGroups = anagramGroups.size();



        // For storing groups of anagrams.

        ArrayList> groups = new ArrayList>(totalGroups);



        for(int i = 0; i < totalGroups; i++) {

            groups.add(new ArrayList());

        }



        int groupNumber = 0;



        // Iterate through the HashMap.

        for (HashMap.Entry> i : anagramGroups.entrySet()) {

            // Insert all strings of the key into one group.

            for (int j : i.getValue()) {

                groups.get(groupNumber).add(strList.get(j));

            }

            groupNumber++;

        }

        

        return groups;

    }

}

Accepted Answer

Trie based Approach

The idea is to sort each string and insert it into the trie. Each node of trie will have an array to store the indexes of the string ending at that node. Using a trie will improve the access time of the elements when compared to HashMap, hence it will be more efficient than using a HashMap.

The structure of the trie class will be:

class TrieNode
{
public:
    TrieNode *children[26];
    vector index;


    TrieNode()
    {
        for (int i = 0; i < 26; i++)
        {
            children[i] = NULL;
        }
    }
    ~TrieNode()
    {
        for (int i = 0; i < 26; i++)
        {
            if (children[i] != NULL)
            {
                delete children[i];
            }
        }
        index.clear();
        index.resize(0);
    }
};

The array “children” stores the pointers to the children nodes of the current node

The steps are as follows :

Define a trie class which has pointers to the children nodes and an additional array as a member to store the indices of strings.
Iterate through all the strings.
1. Store the current string in a temporary variable, let’s say “temp”.
2. Sort the string “temp”.
3. Insert the string “temp” into the trie.
4. Also, push the index of the string in the “index” array of the node of the trie where the last character of the string is stored.
Now we will traverse all the nodes of the trie and for each node of the trie, we will group all strings which end at one node.
1. Define a function traversal(curr) to traverse the trie. Here, “curr” denotes the current node.
2. Iterate through “curr->index” and group all the strings ending at the current node.
3. Iterate through the “children” array and recursively traverse the trie.

Space Complexity: OtherExplanation:

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 trie. There will be ‘N’ strings to insert and in the worst case when no strings have a common prefix the trie will have O(N * (|S|)) nodes. Thus, the total space complexity will be O(N * (|S|)).

Time Complexity: OtherExplanation:

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 each string into the trie. There will be ‘N’ strings to insert and each string will take |S| time to insert into the trie. Thus, the total time complexity will be O(N * (|S| * log(|S|)).

Python (3.5)

'''

    Time Complexity: 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.

'''



# Class TrieNode

class TrieNode :

    

    def __init__(self):

        

        self.children = [None] * 26

        self.index = []

        

class Solution:

    def insert(self, s, head, ind):

        temp = head

        chars = list(s)

        chars.sort()

        

        for i in chars:

            

            # Check if the child exists.

            if temp.children[ord(i) - 97] == None:

                # Creating a new child.

                temp.children[ord(i) - 97] = TrieNode()

                

            temp = temp.children[ord(i) - 97]

        

        temp.index.append(ind)

    

    # Function to group all anagrams together.

    def groupStrings(self, head, groups, strList):

        if head == None:

            return

        

        currGroup = []

        

        # Traverse all strings ending at the current node.

        for i in head.index:

            currGroup.append(strList[i])

            

        if len(currGroup) > 0:

            groups.append(currGroup)

           

        # Iterate thorugh the children.

        for i in range (26):

            self.groupStrings(head.children[i], groups, strList)

    

    def result(self, strList):

        head = TrieNode()

        n = len(strList)

        

        for i in range (n):

            self.insert(strList[i], head, i)

         

        # For storing anagrams.

        groups = []

        self.groupStrings(head, groups, strList)

        

        return groups



def groupAnagramsTogether(strList):

    

    s = Solution()

    return s.result(strList)

C++ (g++ 5.4)

/*

    Time Complexity: 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.

*/



#include 



// Class for Trie.

class TrieNode

{

public:

    TrieNode *children[26];

    vector index;



    TrieNode()

    {

        for (int i = 0; i < 26; i++)

        {

            children[i] = NULL;

        }

    }

    ~TrieNode()

    {

        for (int i = 0; i < 26; i++)

        {

            if (children[i] != NULL)

            {

                delete children[i];

            }

        }

        index.clear();

        index.resize(0);

    }

};



void insert(string s, TrieNode *head, int ind)

{

    TrieNode *temp = head;



    // Sort the string.

    sort(s.begin(), s.end());



    // Iterate through the given string

    for (char i : s)

    {

        // If child node is not present.

        if (temp->children[i - 'a'] == NULL)

        {

            // Create new child node.

            temp->children[i - 'a'] = new TrieNode();

        }

        // Move to the child node.

        temp = temp->children[i - 'a'];

    }



    temp->index.push_back(ind);

}



// Function to group all anagrams together.

void groupStrings(TrieNode *head, vector> &groups, vector &strList)

{

    if (head == NULL)

    {

        return;

    }

    vector currGroup;



    // Traverse all strings ending at the current node.

    for (int i : head->index)

    {

        // Group all strings ending at the current node.

        currGroup.push_back(strList[i]);

    }

    

    if (currGroup.size() > 0)

    {

        groups.push_back(currGroup);

    }



    // Iterate thorugh the children.

    for (int i = 0; i < 26; i++)

    {

        groupStrings(head->children[i], groups, strList);

    }

}



vector> groupAnagramsTogether(vector &strList)

{

    TrieNode *head = new TrieNode();



    int n = strList.size();



    for (int i = 0; i < n; i++)

    {

        insert(strList[i], head, i);

    }



    // For storing groups of anagrams.

    vector> groups;



    groupStrings(head, groups, strList);



    // Free the memory.

    delete head;



    return groups;

}

Java (SE 1.8)

/*

    Time Complexity: 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.

*/



import java.util.Arrays;

import java.util.ArrayList;



// Class for Trie.

class TrieNode {

	public TrieNode []children;

	public ArrayList index;



	TrieNode() {

		children = new TrieNode[26];

		index = new ArrayList();



		for (int i = 0; i < 26; i++) {

			children[i] = null;

		}

	}

}



public class Solution {

	private static void insert(String s, TrieNode head, int ind) {

		TrieNode temp = head;



		// Sort the string.

		char[] chars = s.toCharArray();

		Arrays.sort(chars);



		// Iterate through the given string

		for (char i : chars) {

		

			// If child node is not present.

			if (temp.children[i - 'a'] == null) {

				// Create new child node.

				temp.children[i - 'a'] = new TrieNode();

			}

			// Move to the child node.

			temp = temp.children[i - 'a'];

		}



		temp.index.add(ind);

	}



	// Function to group all anagrams together.

	private static void groupStrings(TrieNode head, ArrayList> groups, ArrayList strList) {

		if (head == null) {

			return;

		}



		ArrayList currGroup = new ArrayList();



		// Traverse all strings ending at the current node.

		for (int i : head.index) {

			// Group all strings ending at the current node.

			currGroup.add(strList.get(i));

		}



		if (currGroup.size() > 0) {

			groups.add(currGroup);

		}



		// Iterate thorugh the children.

		for (int i = 0; i < 26; i++) {

			groupStrings(head.children[i], groups, strList);

		}

	}



	public static ArrayList> groupAnagramsTogether(ArrayList strList) {

		TrieNode head = new TrieNode();



		int n = strList.size();



		for (int i = 0; i < n; i++) {

			insert(strList.get(i), head, i);

		}



		// For storing groups of anagrams.

		ArrayList> groups = new ArrayList>();



		groupStrings(head, groups, strList);



		return groups;

	}

}

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

Note :

Example:

Input Format:

Output Format :

Note:

Constraints :

Top Goldman Sachs Analyst interview questions & answers

Popular interview questions of Analyst

Top HR questions asked in Goldman Sachs Analyst