Group Anagrams Problem in DSA (Simple Explanation with Code)

Introduction

The Group Anagrams problem is a common question in DSA interviews, especially in the string and hashing categories. This problem helps interviewers understand how well you can organize data using logic and data structures.

In simple words, the problem asks you to put words that look different but contain the same characters into the same group.

This article explains every part of the problem in easy language, so even beginners can understand it clearly.

What is an Anagram?

An anagram is formed when two or more words contain the same characters with the same frequency, but the characters may appear in a different order.

This means:

Characters must be the same
Count of each character must be the same
Order of characters does not matter

Examples of Anagrams

"eat" and "tea"
"listen" and "silent"
"rat" and "tar"

If two words meet these conditions, they are anagrams of each other.

What is the Group Anagrams Problem?

You are given a list (array) of strings. Your task is to group all words that are anagrams of each other.

Each group should contain only those words that are anagrams.

Example

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

Explanation

"eat", "tea", and "ate" contain the same characters → one group
"tan" and "nat" contain the same characters → second group
"bat" has no matching anagram → separate group

Why Brute Force Approach is Not Good

In the brute-force approach, we compare every word with every other word to check whether they are anagrams.

Problems with Brute Force

Too many comparisons
Difficult to manage large input sizes
Time Complexity becomes O(n² × k), where k is word length

Because of these reasons, brute force is not suitable for interviews.

Optimized Approach Using HashMap

The most efficient way to solve this problem is by using a HashMap.

Key Idea Behind HashMap Approach

Sort each word alphabetically
Use the sorted word as a key
All anagrams will have the same sorted form

This allows us to group anagrams easily.

Step-by-Step Explanation

Let us understand the logic clearly.

Steps:

Create a HashMap where:
- Key = sorted version of the word
- Value = list of original words
Take each word from the array
Sort its characters
Use the sorted word as the key in the map
Add the original word to the corresponding list
After processing all words, return all values from the map

Dry Run Example

Words: ["eat", "tea", "tan", "ate", "nat", "bat"]

Word	Sorted Form	Grouping
eat	aet	[eat]
tea	aet	[eat, tea]
tan	ant	[tan]
ate	aet	[eat, tea, ate]
nat	ant	[tan, nat]
bat	abt	[bat]

Code Implementation

C++ Code

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> map;

    for (string word : strs) {
        string key = word;
        sort(key.begin(), key.end());
        map[key].push_back(word);
    }

    vector<vector<string>> result;
    for (auto pair : map) {
        result.push_back(pair.second);
    }
    return result;
}

Java Code

public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> map = new HashMap<>();

    for (String word : strs) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(word);
    }

    return new ArrayList<>(map.values());
}

Python Code

def groupAnagrams(strs):
    groups = {}

    for word in strs:
        key = ''.join(sorted(word))
        if key not in groups:
            groups[key] = []
        groups[key].append(word)

    return list(groups.values())

Time and Space Complexity

Time Complexity: O(n × k log k), where k is the length of each word
Space Complexity: O(n)

This approach is efficient and works well for large inputs.

Edge Cases to Consider

Empty list of strings
Single word input
Words containing repeated characters

Testing these cases ensures correctness.

Common Interview Variations

Group anagrams without sorting characters
Count number of anagram groups
Check if two strings are anagrams

Most string-hashing problems are based on similar logic.

Summary

The Group Anagrams problem is an important DSA question that helps you understand how to group related data using hashing. By sorting each word and using it as a key, we can efficiently group all anagrams together. This approach avoids unnecessary comparisons and works well for large inputs. Mastering this problem will strengthen your understanding of strings and HashMap-based solutions, which are commonly tested in coding interviews.