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:

1. Create a HashMap where:

   • Key = sorted version of the word

   • Value = list of original words

2. Take each word from the array

3. Sort its characters

4. Use the sorted word as the key in the map

5. Add the original word to the corresponding list

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