Group Anagrams DSA Solution - Hash Key Pattern - Study Chapter | QuizMaker

Group Anagrams explained with brute force, optimized hash key grouping, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 2: Strings

Learning Outcome

After this lesson, you should be able to convert each word into a canonical key and use that key to group equivalent strings.

Problem Statement

Given an array of strings, group the anagrams together. The order of groups usually does not matter.

Input	Output	Why
`["eat","tea","tan","ate","nat","bat"]`	`[["eat","tea","ate"],["tan","nat"],["bat"]]`	Words with the same character counts are grouped.

Brute Force Approach

Compare every word with existing groups by checking whether it is an anagram of the group representative.

This repeats anagram checks many times and becomes harder to manage as the input grows.

Optimized Approach

Create a canonical key for each word. A common key is the sorted word. All anagrams produce the same sorted key, so they can be grouped in a hash map.

If the alphabet is fixed, a frequency-count key also works and can avoid sorting each word.

Exact Pseudocode

groups = empty map from key to list
for word in words:
  key = sorted characters of word
  append word to groups[key]
return all values from groups

Reference Code

class Solution:
    def groupAnagrams(self, strs):
        groups = {}

        for word in strs:
            key = "".join(sorted(word))
            groups.setdefault(key, []).append(word)

        return list(groups.values())

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;

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

        vector<vector<string>> result;
        for (auto& entry : groups) {
            result.push_back(entry.second);
        }
        return result;
    }
};

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : strs) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }

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

Sample Dry Run

word	key	map action
`eat`	`aet`	Create group `aet -> [eat]`
`tea`	`aet`	Append to `aet`
`tan`	`ant`	Create group `ant -> [tan]`
`ate`	`aet`	Append to `aet`

Complexity

Measure	Value	Reason
Time	O(n * k log k)	There are `n` words and each word of length `k` is sorted.
Space	O(n * k)	The groups store all words and keys.

Edge Cases

Empty string as a word.
Single-word input.
Duplicate words should appear in the output group.

Interview Checklist

Explain the canonical key clearly.
Mention sorted key versus frequency key tradeoff.
Do not compare every word pair.

FAQs

Why does sorting form a valid key?

Anagrams have exactly the same characters, so their sorted forms are identical.

Can frequency counts be used instead?

Yes. For lowercase English letters, a 26-count tuple is also a strong key.

What is the core pattern?

Hash map grouping by canonical key.