Developers

Group Anagrams

MediumHashing and countingGrade BAlso known as LeetCode 49

You are given a list of strings strs. Group the strings that are anagrams of one another and return the groups. Two strings are anagrams when one can be rearranged into the other, which means they have the same letters with the same counts.

The groups may be returned in any order, and the strings inside a group may be in any order. Every string appears in exactly one group, and an empty string is an anagram of another empty string.

Examples

Input strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
Any order of the groups and of the words inside them is accepted.
Input strs = [""]
Output [[""]]
Input strs = ["a"]
Output [["a"]]

Constraints

  • 1 <= strs.length <= 10,000
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters

Stuck? Take one hint at a time

Common mistakes
  • Using the sorted word as the key but forgetting to join the letters into a string, in a language where a list of characters cannot be a map key.
  • Using the sum or the product of the letters as the key. Different words can have the same sum, so they would be grouped wrongly.
  • Building the count key without a separator when counts can be more than one digit, so that "1" followed by "11" looks like "11" followed by "1".
  • Comparing each word with every other word, which is quadratic in the number of words.
Questions an interviewer may ask next
  • The words may contain any Unicode characters. Which key still works, and what does the count version need instead of 26 slots?
  • Return the groups in the order in which their first word appears in the input, and keep the words in each group in input order. What changes? (An ordered map, or a list of keys in first seen order.)
  • Find only the groups that have at least two words.
  • The list is too big for memory. How could you group the words using external sorting? (Sort the pairs of (key, word) by key.)

How often this is reported

Commonly reported across 14 of 25 tracked companies
14/25

Grade B: Reported in more than one source. This reflects what candidates report, not a guarantee of what any company will ask.