Group Anagrams

Question

Given an array of strings, group the anagrams together. Explore sorting-based and hash-based approaches. Commonly asked in Meta phone screens and onsite coding rounds.

Codemia · Accepted Answer

To group anagrams, we need to identify strings that can be rearranged to form one another. The most effective pattern for this problem is the use of a hash-based approach, specifically utilizing a dictionary to group strings by their sorted character representation. Since anagrams share the same characters, sorting each string will allow us to use the sorted string as a unique key for our dictionary. For example, both 'eat' and 'tea' will become 'aet' when sorted, allowing us to group them together.

1. Initialize an empty dictionary to hold our groups of anagrams.
2. Iterate through each string in the input array:
   - For each string, sort its characters to get a key (e.g., 'eat' -> 'aet').
   - Check if this key already exists in the dictionary:
     - If it does, append the original string to the list corresponding to this key.
     - If it doesn’t, create a new entry in the dictionary with the key and start a new list containing the original string.
3. Finally, return the values of the dictionary, which will contain lists of grouped anagrams.

Example: Given the input ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'], the sorted keys would be:
- 'eat' -> 'aet'
- 'tea' -> 'aet'
- 'tan' -> 'ant'
- 'ate' -> 'aet'
- 'nat' -> 'ant'
- 'bat' -> 'abt'

This results in the dictionary:
{
 'aet': ['eat', 'tea', 'ate'],
 'ant': ['tan', 'nat'],
 'abt': ['bat']
}
The output will be [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']].

Here’s the implementation in Python:
```python
from collections import defaultdict

def group_anagrams(strs):
    anagrams = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))  # Create a sorted string as the key
        anagrams[key].append(s)  # Append the original string to the list
    return list(anagrams.values())  # Return the grouped anagrams
```
This solution uses `defaultdict` from the collections module to simplify the process of appending to the lists.

The time complexity of this solution is O(N * K log K), where N is the number of strings and K is the maximum length of a string. This accounts for sorting each string, which is O(K log K), and we do this for each of the N strings. The space complexity is O(N) for storing the anagrams in the dictionary. This is efficient given that we must store all the strings at least once.

1. Empty List: If the input list is empty, the output should also be an empty list: `[]`.
2. Single String: If the input contains only one string, the output should be a list containing that string: `[['a']]` for input `['a']`.
3. All Unique Strings: If no strings are anagrams of each other, each string should be its own group: input `['abc', 'def', 'ghi']` results in `[['abc'], ['def'], ['ghi']]`.
4. Case Sensitivity: If the input contains strings with mixed cases, such as `['abc', 'ABC']`, they will not be grouped together unless specified to be case insensitive.

Group Anagrams

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string