Sweaty Imposter

Group Anagrams

MediumArrays & HashingBlind 75MidOpen on LeetCodeUpdated

You're given an array of strings strs. Group together the strings that are anagrams of each other, meaning one can be turned into the other by reordering its letters (same letters, same counts). Return a list of groups, where each group is a list of strings. Every input string appears in exactly one group, repeated strings included. The groups, and the strings inside each group, may be returned in any order. The empty string is a valid word.

Examples

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

"eat", "tea" and "ate" each use one a, one e and one t, so they form a group. "tan" and "nat" share a, n and t, while "bat" has no partner and stands alone.

strs = [""] returns [[""]]

The empty string is still a word, so it forms a group of its own.

strs = ["aab","aba","abb","aab"] returns [["aab","aba","aab"],["abb"]]

"aab", "aba" and the repeated "aab" all have two a's and one b. "abb" uses the same two letters but with two b's, so it is not an anagram of them. Both copies of "aab" stay in the output.

Constraints

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

Hints

Hint 1

Two words are anagrams exactly when they contain the same letters the same number of times. What value could you compute from a word so that all of its anagrams produce the same value?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Anagrams have identical letter counts, so a word's 26-entry count is a key that every one of its anagrams shares. Walk the strings once, count each word's letters, turn the count into a hashable key (a tuple in Python, a string in Java) and append the word to that key's list in a hash map. The map's values are the groups. With n strings of length at most k this is O(n * k); using each word's sorted letters as the key also works but costs O(n * k log k).

Time

O(n * k)

Space

O(n * k)

Pitfall

Using the raw count array as the key. Python lists are unhashable and Java int[] arrays hash by identity, so equal counts land in different buckets; convert the count to a tuple or string first.

Solutions

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) count[c - 'a']++;
            String key = Arrays.toString(count);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}
Drill This