Group Anagrams

Problem Link - Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

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.

Intuition && Approach

• Anagrams are words or phrases that are formed by rearranging the letters of another, using all the original letters exactly once.


• To identify anagrams, if the count of number of characters in 2 words are same, then it is an anagram. this means if we sort the 2 words then we get the same result.


• So we declare a hashmap that stores the key-value pairs, where key is the sorted version of the word and values are the list of all words that matches this key whose sorted version is same.
  


• So we iterate through the list of words, for each we will find the sorted version of that word, and find the key in map and update its value list by adding this word.

Code

#include <bits/stdc++.h> 

using namespace std;



vector<vector<string>> getGroupedAnagrams(vector<string> &input,int n) {

    // Using an unordered map to group anagrams

    unordered_map<string, vector<string>> mp;



    for (const string& str : input) {

        string temp = str; // Copy the original string

        sort(temp.begin(), temp.end()); // Sort the string to find the key

        mp[temp].push_back(str); // Group anagrams together

    }



    // Prepare the result from the map

    vector<vector<string>> ans;

    for (const auto& it : mp) {

        ans.push_back(it.second);

    }



    return ans;

}

Time Complexity: O(n * m(log m)), where m is the length of a word.

A single traversal through the array is needed.

Space Complexity: O(n).

There are n words in a string. The map requires O(n) space to store the strings.