# Solution For Group Anagrams

Problem Statement:

Given an array of strings, group anagrams together.

Example:

Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] Output: [ [“ate”,”eat”,”tea”], [“nat”,”tan”], [“bat”] ]

Solution:

To solve this problem, we can utilize the fact that two strings are anagrams if and only if they have the same set of characters. In other words, if we sort the characters in each string and group strings with the same sorted form together, we will obtain groups of anagrams.

Algorithm:

1. Create an empty dictionary to store groups of anagrams.
2. Iterate through each string in the input array:
a. Sort the characters in the string.
b. Use the sorted string as a key to store the original string in the dictionary.
3. Return the values of the dictionary as the grouped anagrams.

Code:

Here’s the Python code that implements the above algorithm:

“`python
from typing import List

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
# Create an empty dictionary to store groups of anagrams
anagrams = {}

``````    # Iterate through each string in the input array
for s in strs:
# Sort the characters in the string
sorted_s = "".join(sorted(s))

# Use the sorted string as a key to store the original string in the dictionary
if sorted_s not in anagrams:
anagrams[sorted_s] = [s]
else:
anagrams[sorted_s].append(s)

# Return the values of the dictionary as the grouped anagrams
return list(anagrams.values())
``````

“`

Complexity Analysis:

• Time complexity: O(nklogk) where n is the number of strings and k is the maximum length of a string. The time complexity is dominated by the cost of sorting each string.
• Space complexity: O(nk) to store the dictionary and the output array.

## Step by Step Implementation For Group Anagrams

```import java.util.*;

class Solution {
public List 	> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList();
Map ans = new HashMap();
for (String s : strs) {
char[] ca = s.toCharArray();
Arrays.sort(ca);
String key = String.valueOf(ca);
if (!ans.containsKey(key)) ans.put(key, new ArrayList());
}
return new ArrayList(ans.values());
}
}

//Time Complexity: O(NKlogK), where N is the length of strs, and K is the maximum length of a string in strs.
//The outer loop has complexity O(N) as we iterate through each string. Then, we sort each string in O(KlogK) time.```
```def groupAnagrams(strs):
ans = collections.defaultdict(list)
for s in strs:
count =  * 26
for c in s:
count[ord(c) - ord('a')] += 1
ans[tuple(count)].append(s)
return ans.values()```
```var groupAnagrams = function(strs) {
// create a map to store our anagram groups
const map = new Map();
// loop through each string in the input array
for (const str of strs) {
// create a key by sorting the string
const key = str.split('').sort().join('');
// if the key exists in the map, push the current string into the corresponding group
if (map.has(key)) {
map.get(key).push(str);
// if the key does not exist in the map, create a new group with the current string
} else {
map.set(key, [str]);
}
}
// return the values of the map as our results
return [...map.values()];
};```
```vector> groupAnagrams(vector& strs) {
// create a map of vector of strings to store the grouped anagrams
map, vector> anagrams;

// iterate over each string in the input vector
for (string str : strs) {
// create a vector of characters to store the current string
vector chars(str.begin(), str.end());

// sort the characters in the vector
sort(chars.begin(), chars.end());

// check if the map already contains an entry for the sorted vector of characters
if (anagrams.find(chars) != anagrams.end()) {
// if an entry exists, retrieve the vector of strings associated with the sorted vector of characters
vector& group = anagrams[chars];

// add the current string to the vector of strings
group.push_back(str);
} else {
// if an entry does not exist, create a new vector of strings with the current string
vector group = {str};

// insert the new vector of strings into the map
anagrams.insert({chars, group});
}
}

// create a vector of vector of strings to store the grouped anagrams
vector> groupedAnagrams;

// iterate over each entry in the map
for (auto entry : anagrams) {
// retrieve the vector of strings associated with the entry
vector group = entry.second;

// add the vector of strings to the grouped anagrams vector
groupedAnagrams.push_back(group);
}

// return the grouped anagrams vector
return groupedAnagrams;
}```
```using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
public IList> GroupAnagrams(string[] strs) {
// create a dictionary to store the anagram groups
Dictionary> dict = new Dictionary>();

// go through each string in the input array
foreach(string s in strs) {
// create a key by sorting the string characters alphabetically
// this will group anagrams together
string key = String.Concat(s.OrderBy(c => c));

// check if the key already exists in the dictionary
if(dict.ContainsKey(key)) {
// if it does, add the current string to the list of anagrams