Group Anagrams Explained: Grouping ["eat","tea","tan",...]

Imagine you are handed a messy box of word cards: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]. Your goal is to tidy them up into piles where every word in a pile is an anagram of the others. Without a smart strategy, you might find yourself constantly comparing every single word against every other word, checking if their letters match. For a tiny list of six words, that is tedious. For a dictionary of thousands of words, doing pairwise comparisons becomes a slow nightmare.

Anagrams share an invisible DNA: they use the exact same letters in different orders. For instance,

To group anagrams efficiently without comparing every word against every other word, we need a way to assign them a single, unmistakable identity. In our working example with strs = ["eat","tea","tan","ate","nat","bat"], words like "eat", "tea", and "ate" look completely different on the surface. However, if you sort the letters of each word alphabetically, all three transform into the exact same string: "aet".

This sorted character sequence acts as a signature or bucket key. Instead of treating words as isolated strings, we view them as containers of letter counts. Every word that shares the exact same letter composition produces the identical signature, making it a natural identifier for a hash map.

We can picture our grouping process as a dictionary where the keys are these sorted signatures and the values are lists of original words that produced them:

- Key "aet" $\to$ ["eat", "tea", "ate"]
- Key "ant" $\to$ ["tan", "nat"]
- Key "abt" $\to$ ["bat"]

By establishing this model, the chaotic task of finding anagrams simplifies into a two-step routine for each word: compute its signature, and drop the original word into the corresponding bucket.

Let us trace the algorithm using our locked example: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]. We will maintain a hash map where the keys are canonical signatures (sorted character strings) and the values are lists of original words that share that signature.

Steps

1. First item ("eat"): Sort characters to get signature "aet". Map is currently empty. Insert key "aet" with value ["eat"].
* Map: {"aet": ["eat"]}
2. Second item ("tea"): Sort characters to get signature "aet". Key "aet" already exists. Append "tea" to its list.
* Map: {"aet": ["eat", "tea"]}
3. Third item ("tan"): Sort characters to get signature "ant". Key does not exist. Insert key "ant" with value ["tan"].
* Map: {"aet": ["eat", "tea"], "ant": ["tan"]}
4. Fourth item ("ate"): Sort characters to get signature "aet". Key exists. Append "ate" to its list.
* Map: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
5. Fifth item ("nat"): Sort characters to get signature "ant". Key exists. Append "nat" to its list.
* Map: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
6. Sixth item ("bat"): Sort characters to get signature "abt". Key does not exist. Insert key "abt" with value ["bat"].
* Final Map: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

Result

Extracting all values from the final hash map yields [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Try this: Given the intermediate map state {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}, explain precisely what happens when the word "nat" is processed next.

Now that you have seen how sorting characters into a canonical signature transforms the chaotic list ["eat","tea","tan","ate","nat","bat"] into predictable buckets like ["eat","tea","ate"], ["tan","nat"], and ["bat"], it is time to apply this exact same abstraction elsewhere. The core design pattern here is not just about anagrams—it is about compression through canonical representation. Whenever you have items that look different on the surface but share an underlying structural equivalence, you can design a deterministic function to map them to a shared lookup key.

Consider a neighboring problem: suppose you are given a list of strings and need to group together all words that can be formed by shifting their letters cyclically by some offset (like Caesar cipher shifts, where abc and bcd are equivalent). Just as sorting characters gave us a canonical key for anagrams, what deterministic signature function could you design to group shifted strings, and how would your hash map structure change?