Logo for ammarahmed.ca
Medium
May 24, 2025
#arrays
#hashing

49. Group Anagrams

Problem

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 <= 104
          • 0 <= strs[i].length <= 100
            • strs[i] consists of lowercase English letters.

              Approach

              This question builds upon the Valid Anagram's question. We'll use the same approach of counting letter frequencies using a constant size array of 26 values, however, now we want to track multiple anagrams. We can use a hashmap to store the frequency arrays as the keys and an array of strings as it's values. We start by iterating over the strings. For each word, we create it's frequency array. Then, we check if that specific frequency array exists in the hashmap. If it does, we add that string to it's value array. If it doesn't, we create a new entry in the hashmap with that frequency array as the key and an array of strings with that string as it's first value as the hashmap value. To create the result, we simply iterate over the hashmap and combine all the values.

              Complexity

              Time: O(n)

              We iterate over the input array once (O(n)) and we also iterate over the hash map once, which could potentially have n values (O(n))

              Space: O(n)

              The hash map can potentially contain n entries

              Solution

              1func groupAnagrams(strs []string) [][]string { 2 group := make(map[[26]int][]string) 3 4 for _, str := range strs { 5 var freq [26]int 6 for _, ch := range str { 7 freq[ch - 'a']++ 8 } 9 10 if words, exists := group[freq]; exists { 11 group[freq] = append(words, str) 12 } else { 13 group[freq] = []string{str} 14 } 15 } 16 17 var result [][]string 18 for _, value := range group { 19 result = append(result, value) 20 } 21 return result 22}