Group Anagrams

49. Group Anagrams

Medium

Group the anagrams together from an array of strings.

ArrayHash TableStringSorting

View Problem

Problem Statement

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

Try It Yourself

TypeScript

function groupAnagrams(strs: string[]): string[][] {
    // Your solution here
}

Go

func groupAnagrams(strs []string) [][]string {
    // Your solution here
}

Solution

Click to reveal solution

Use a hash map where the key is the sorted string and the value is an array of anagrams.

TypeScript Solution

function groupAnagrams(strs: string[]): string[][] {
  const hashmap = {}

  for (const str of strs) {
      const sorted = str.split("").toSorted().join("");
      hashmap[sorted] ||= [];
      hashmap[sorted].push(str);
  }

  const res = [];
  Object.values(hashmap).forEach(arr => res.push(arr));
  return res;
}

Time:O(n * k log k)

Space:O(n * k)

Go Solution

import (
  "strings"
  "slices"
)

func groupAnagrams(strs []string) [][]string {
  hashmap := map[string][]string{}

  for _, str := range strs {
      splitted := strings.Split(str, "")
      slices.Sort(splitted)
      sortedStr := strings.Join(splitted, "")

      _, ok := hashmap[sortedStr]
      if ok {
          hashmap[sortedStr] = append(hashmap[sortedStr], str)
      } else {
          hashmap[sortedStr] = []string{str}
      }
  }

  res := [][]string{}

  for _, val := range hashmap {
      res = append(res, val)
  }

  return res
}

Time:O(n * k log k)

Space:O(n * k)

Algorithm:

1. Create a hash map to group strings by their sorted characters
2. For each string in the input array:
   • Sort the characters to create a key
   • Add the original string to the group for that key
3. Convert the hash map values to the result array
4. Return the grouped anagrams

Time Complexity: O(n * k log k) where n is the number of strings and k is the maximum length of a string Space Complexity: O(n * k) for storing all strings in the hash map

Alternative Approach (Character Counting): Instead of sorting, you could use character frequency counting as the key, which would give O(n * k) time complexity:

function groupAnagrams(strs: string[]): string[][] {
    const hashmap = new Map<string, string[]>();

    for (const str of strs) {
        const count = new Array(26).fill(0);
        for (const char of str) {
            count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        const key = count.join(',');
        
        if (!hashmap.has(key)) {
            hashmap.set(key, []);
        }
        hashmap.get(key)!.push(str);
    }

    return Array.from(hashmap.values());
}