Group Anagrams

MEDIUM

Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = ["a"]

Output: [["a"]]

Constraints:

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

Approaches

Checkout 3 different approaches to solve Group Anagrams. Click on different approaches to view the approach and algorithm in detail.

Grouping with Character Count as Keys

This approach is an optimization over the sorting method. Instead of sorting, we create a canonical key for each string based on its character counts. Two strings are anagrams if and only if they have the same character counts.

Algorithm

Initialize a hash map map where key is a String and value is a List<String>.
Iterate through each string s in the input array strs.
Create an integer array count of size 26, initialized to zeros.
For each character c in s, increment count[c - 'a'].
Build a key string from the count array. A simple way is to append each count value preceded by a delimiter (e.g., #) to a StringBuilder.
Use this generated key to store the original string s in the map, creating a new list if the key is new.
After iterating through all strings, return a new list containing the values of the map.

We use a hash map, similar to the previous approach. However, the key is generated differently. For each string, we compute its character frequency. Since the strings only contain lowercase English letters, we can use an integer array of size 26 for this. After counting, we need to convert this frequency array into a unique, hashable key. A common way is to create a string representation. For example, an array [1, 2, 0, ...] (one 'a', two 'b's) can be converted to a string like "1#2#0#...". We iterate through the input strs. For each string s, we calculate its character count array. We then build a key string from this count array. This key is used to store the original string s in the hash map. Finally, we return the lists of strings from the map's values. This method avoids the O(K log K) sorting cost, replacing it with a linear O(K) scan.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

Complexity Analysis

Time Complexity: O(N * K)Space Complexity: O(N * K)

Pros and Cons

Pros:

Most efficient time complexity among the three approaches.
Avoids the log K factor associated with sorting.

Cons:

The key generation is slightly more complex than simply sorting the string.

Code Solutions

Checking out 4 solutions in different languages for Group Anagrams. Click on different languages to view the code.

class Solution {
public
  List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> d = new HashMap<>();
    for (String s : strs) {
      char[] t = s.toCharArray();
      Arrays.sort(t);
      String k = String.valueOf(t);
      d.computeIfAbsent(k, key->new ArrayList<>()).add(s);
    }
    return new ArrayList<>(d.values());
  }
}

Video Solution

Watch the video walkthrough for Group Anagrams

Algorithms:

Sorting

Data Structures:

ArrayHash TableString

Companies:

Accenture |Adobe |Agoda |Amazon |