DSA Tracker

Visualize

Group Anagrams

Every anagram shares the same sorted-letter key (e.g. "eat" and "tea" both sort to "aet"). Bucket each word by that key in a map, then return the buckets. Reach for it whenever grouping strings by a shared signature.

Details

Animated on: ["eat","tea","tan","ate","nat","bat"] — group words that are anagrams of each other

Problem:Group AnagramsMedium

Pattern:Hashing and Frequency Maps

Strings

step 1 / 8

eat
[0]
tea
[1]
tan
[2]
ate
[3]
nat
[4]
bat
[5]

For each word, sort its letters into a key and drop it into that key's bucket.

Pseudocode
1FUNCTION groupAnagrams(words):
2  make an empty lookup table (sorted-letters key -> list of words)
3  FOR each word in words:
4    key = the word's letters sorted and joined into a string
5    IF key is not in the table: store key -> an empty list
6    add word to the list stored for key
7  END FOR
8  RETURN all the lists in the table
9END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. For each word, sort its letters into a key and drop it into that key's bucket.
  2. "eat" sorts to "aet" — new bucket. groups = { aet: [eat] }.
  3. "tea" sorts to "aet" too — same bucket as "eat". groups = { aet: [eat, tea] }.
  4. "tan" sorts to "ant" — new bucket. groups = { aet: [eat, tea], ant: [tan] }.
  5. "ate" sorts to "aet" — joins the first bucket. groups = { aet: [eat, tea, ate], ant: [tan] }.
  6. "nat" sorts to "ant" — joins the second bucket. groups = { aet: [...3], ant: [tan, nat] }.
  7. "bat" sorts to "abt" — new bucket, no other word shares it. groups = { aet: [...3], ant: [...2], abt: [bat] }.
  8. Return the buckets: [["eat","tea","ate"], ["tan","nat"], ["bat"]] — 3 anagram groups from 6 words.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Group Anagrams in the editorAll Strings problemsBack to roadmap