# Group Anagrams Together from given List of Words

Given a list of words, efficiently group all anagrams together.

X and Y are anagrams if by rearranging the letters of X, we can get Y using all the original letters of X exactly once.

For example, all these pairs are anagrams as lhs can be rearranged to rhs and vice-versa –

actors = costar
altered = related
auctioned = education
aspired = despair
mastering = streaming
recursed = secured

The problem requires the anagrams to be grouped together. For example,

Input:

[CARS, REPAID, DUES, NOSE, SIGNED, LANE, PAIRED, ARCS,
GRAB, USED, ONES, BRAG, SUED, LEAN, SCAR, DESIGN]

Output:

GRAB BRAG
CARS ARCS SCAR
REPAID PAIRED
LANE LEAN
SIGNED DESIGN
DUES USED SUED
NOSE ONES

The idea is to sort each individual word in the list and construct a map where map’s key is each sorted word and map’s value is list of indices in the array where it is present. After creating the map, we traverse the map and get indices for each sorted key. The anagrams are present in actual list at those indices.

Below is C++ and Java implementation of the idea –

Output:

GRAB BRAG
LANE LEAN
SIGNED DESIGN
CARS ARCS SCAR
REPAID PAIRED
DUES USED SUED
NOSE ONES

## Java

Output:

REPAID PAIRED
GRAB BRAG
LANE LEAN
DUES USED SUED
CARS ARCS SCAR
NOSE ONES
SIGNED DESIGN

We can also use multimap to solve this problem as demonstrated below:

Output:

ONES NOSE
SUED USED DUES
PAIRED REPAID
SCAR ARCS CARS
LEAN LANE
DESIGN SIGNED
BRAG GRAB

## Java

Output:

REPAID PAIRED
GRAB BRAG
LANE LEAN
DUES USED SUED
CARS ARCS SCAR
NOSE ONES
SIGNED DESIGN

The time complexity of above solutions is O(nmlogm) where n is number of words and m is size of longest word in the list.