Group Anagrams: Hash key Pattern

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.

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())
  

Sample Dry Run

Complexity

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