MediumHash map

Group Anagrams

Q: Why Hash.new with a block and not Hash.new([])?

Hash.new([]) returns the same array object as the default for every missing key and never stores it, so groups[key] << word pushes every word into that one shared array and the hash stays empty. The block form, Hash.new { |h, k| h[k] = [] }, creates a fresh array per key and stores it.

Q: Is it safe to use an array as a hash key?

Yes, as long as you do not mutate it afterwards. counts is a fresh array for each word and is never changed once it is a key. If you did change a key array, its hash would no longer match and you would need groups.rehash.

Q: Is sort.join faster than counting in Ruby?

For short words, usually yes: chars.sort.join runs mostly in C, while the counting loop runs a Ruby block per byte. Counting only wins on long words, where O(k) beats O(k log k). each_byte is the cheapest way to walk the letters, because it does not build a string per character the way each_char does.

Q: Can I use each_with_object instead?

Yes: strs.each_with_object(Hash.new { |h, k| h[k] = [] }) { |w, h| h[w.chars.sort.join] << w }.values builds the same groups. group_by says the same thing more directly, so the sorted-key solution uses it.

Q: What does chars.tally return?

tally counts equal elements and returns a hash such as {"a"=>2, "b"=>1}. Two hashes compare equal with == when they hold the same pairs, in any order, which is exactly the anagram test. It was added in Ruby 2.7.

You get an array of strings strs, each made of lowercase letters a to z. Two strings are anagrams when one is a rearrangement of the other: the same letters, each used the same number of times. Put every string into a group together with all of its anagrams and return the groups as an array of arrays of strings.

The groups can come in any order, but inside a group the strings must keep the order they had in strs. Every string belongs to exactly one group, a string with no anagram forms a group of its own, and a string that appears several times appears in its group once per copy. The empty string is allowed and is an anagram only of another empty string. An empty strs returns an empty array.

Examples

Input

strs = ["race", "care", "arc", "acre", "car", "cat"]

Output[["race", "care", "acre"], ["arc", "car"], ["cat"]]Whyrace, care and acre use the same four letters, arc and car the same three. cat has no partner, so it is a group of one. Inside each group the words keep their input order.

Input

strs = ["", "b", "", "bb"]

Output[["", ""], ["b"], ["bb"]]WhyThe two empty strings are anagrams of each other. b and bb are not: the counts must match, not only the set of letters.

Constraints

Size: 0 ≤ strs.length ≤ 1,000
Length: 0 ≤ strs[i].length ≤ 20
Letters: strs[i] holds lowercase a–z only
Answer: Groups in any order; inside a group, the input order. Repeated strings stay.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a list of groups. For each word, walk the groups and compare the word with each group's first word; join the first group that matches, or start a new one. is_anagram checks the lengths, then adds one per letter of a and takes one away per letter of b in a 26-slot list: every slot back at zero means the same letters, the same number of times.

def group_anagrams(strs: list[str]) -> list[list[str]]:
    def is_anagram(a: str, b: str) -> bool:
        if len(a) != len(b):
            return False
        counts = [0] * 26
        for ch in a:
            counts[ord(ch) - 97] += 1
        for ch in b:
            counts[ord(ch) - 97] -= 1
        return all(c == 0 for c in counts)

    groups: list[list[str]] = []
    for word in strs:
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return groups

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

Every anagram sorts to the same string, so ''.join(sorted(word)) is a label the whole group shares. A defaultdict(list) files each word under its label, and since the words arrive in input order, each list keeps that order. Dictionaries remember insertion order, so the groups come out in the order their first word appeared.

from collections import defaultdict


def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: defaultdict[str, list[str]] = defaultdict(list)
    for word in strs:
        groups["".join(sorted(word))].append(word)
    return list(groups.values())

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count the letters instead of sorting them: one pass over the word fills a 26-slot list, and tuple(counts) turns it into a hashable key. Building the key is linear in the word length, so the whole function is O(n·k). A tuple keeps the counts apart on its own, so (1, 11, …) and (11, 1, …) never collide.

from collections import defaultdict


def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: defaultdict[tuple[int, ...], list[str]] = defaultdict(list)
    for word in strs:
        counts = [0] * 26
        for ch in word:
            counts[ord(ch) - 97] += 1
        groups[tuple(counts)].append(word)
    return list(groups.values())

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep an array of groups. Each word is compared with the first word of every group so far and joins the first one that matches; find returns undefined when none does, and the word starts a new group. isAnagram checks the lengths, then counts letters up for a and down for b in an Int32Array(26): all zeros means an anagram.

function groupAnagrams(strs) {
  function isAnagram(a, b) {
    if (a.length !== b.length) return false;
    const counts = new Int32Array(26);
    for (let i = 0; i < a.length; i++) {
      counts[a.charCodeAt(i) - 97]++;
      counts[b.charCodeAt(i) - 97]--;
    }
    return counts.every((c) => c === 0);
  }

  const groups = [];
  for (const word of strs) {
    const group = groups.find((g) => isAnagram(g[0], word));
    if (group) group.push(word);
    else groups.push([word]);
  }
  return groups;
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same string, so [...word].sort().join('') is a label the group shares. A Map files each word under its label, and Array.from(groups.values()) returns the lists in the order their first word appeared. Words are pushed in input order, so each group keeps it.

function groupAnagrams(strs) {
  const groups = new Map(); // sorted letters -> words
  for (const word of strs) {
    const key = [...word].sort().join('');
    const group = groups.get(key);
    if (group) group.push(word);
    else groups.set(key, [word]);
  }
  return Array.from(groups.values());
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Counting is linear where sorting is not: one pass fills an Int32Array(26), and counts.join(',') turns it into a string key such as "1,0,2,…". The comma matters: without it, counts of 1 and 11 and counts of 11 and 1 would both read "111…".

function groupAnagrams(strs) {
  const groups = new Map(); // letter counts -> words
  for (const word of strs) {
    const counts = new Int32Array(26);
    for (let i = 0; i < word.length; i++) counts[word.charCodeAt(i) - 97]++;
    const key = counts.join(',');
    const group = groups.get(key);
    if (group) group.push(word);
    else groups.set(key, [word]);
  }
  return Array.from(groups.values());
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a string[][] of groups and compare each word with the first word of every group so far. find returns the first group that matches or undefined, in which case the word starts a new group. isAnagram checks the lengths, then counts letters up for one word and down for the other in an Int32Array.

function groupAnagrams(strs: string[]): string[][] {
  const groups: string[][] = [];
  for (const word of strs) {
    const group = groups.find((g) => isAnagram(g[0], word));
    if (group) group.push(word);
    else groups.push([word]);
  }
  return groups;
}

function isAnagram(a: string, b: string): boolean {
  if (a.length !== b.length) return false;
  const counts = new Int32Array(26);
  for (let i = 0; i < a.length; i++) {
    counts[a.charCodeAt(i) - 97]++;
    counts[b.charCodeAt(i) - 97]--;
  }
  return counts.every((c) => c === 0);
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

Every anagram sorts to the same string, so the sorted word is the key of a Map<string, string[]>. Words are pushed in input order, and the map returns its lists in the order their first word appeared.

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const word of strs) {
    const key = [...word].sort().join('');
    const group = groups.get(key);
    if (group) group.push(word);
    else groups.set(key, [word]);
  }
  return [...groups.values()];
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

One pass over the word fills 26 counters, and counts.join(',') makes a string key that compares by value. That is O(k) per word instead of the O(k log k) sort, and the commas keep counts like 1 and 11 apart from 11 and 1.

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const word of strs) {
    const counts = new Int32Array(26);
    for (let i = 0; i < word.length; i++) counts[word.charCodeAt(i) - 97]++;
    const key = counts.join(',');
    const group = groups.get(key);
    if (group) group.push(word);
    else groups.set(key, [word]);
  }
  return [...groups.values()];
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a List<List<String>> of groups. Each word is compared with the first word of every group so far and joins the first match, or starts a new group. isAnagram checks the lengths, then counts letters up for one word and down for the other in an int[26]. The method returns String[][], so the lists are copied out with toArray(new String[0]) at the end.

import java.util.*;

public class Main {
    static String[][] groupAnagrams(String[] strs) {
        List<List<String>> groups = new ArrayList<>();
        for (String word : strs) {
            List<String> match = null;
            for (List<String> group : groups) {
                if (isAnagram(group.get(0), word)) {
                    match = group;
                    break;
                }
            }
            if (match == null) {
                match = new ArrayList<>();
                groups.add(match);
            }
            match.add(word);
        }
        String[][] result = new String[groups.size()][];
        for (int i = 0; i < groups.size(); i++) result[i] = groups.get(i).toArray(new String[0]);
        return result;
    }

    static boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) return false;
        int[] counts = new int[26];
        for (int i = 0; i < a.length(); i++) {
            counts[a.charAt(i) - 'a']++;
            counts[b.charAt(i) - 'a']--;
        }
        for (int c : counts) if (c != 0) return false;
        return true;
    }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters. toCharArray, Arrays.sort and new String(chars) build that key, and computeIfAbsent fetches the key's list or creates it in one call. A LinkedHashMap keeps the groups in the order their first word appeared; words are added in input order, so each group keeps it too.

import java.util.*;

public class Main {
    static String[][] groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new LinkedHashMap<>();
        for (String word : strs) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            groups.computeIfAbsent(new String(chars), k -> new ArrayList<>()).add(word);
        }
        String[][] result = new String[groups.size()][];
        int i = 0;
        for (List<String> group : groups.values()) result[i++] = group.toArray(new String[0]);
        return result;
    }
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count the letters in an int[26] instead of sorting, which is linear in the word length. An int[] cannot be the key (arrays hash by identity), so Arrays.toString(counts) turns it into a string like "[1, 0, 2, …]", whose separators also keep counts of 1 and 11 apart from 11 and 1.

import java.util.*;

public class Main {
    static String[][] groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new LinkedHashMap<>();
        for (String word : strs) {
            int[] counts = new int[26];
            for (int i = 0; i < word.length(); i++) counts[word.charAt(i) - 'a']++;
            groups.computeIfAbsent(Arrays.toString(counts), k -> new ArrayList<>()).add(word);
        }
        String[][] result = new String[groups.size()][];
        int i = 0;
        for (List<String> group : groups.values()) result[i++] = group.toArray(new String[0]);
        return result;
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a [][]string of groups and compare each word with the first word of every group so far. A labelled continue next skips to the next word as soon as the word joins a group; falling out of the inner loop means no group matched, so the word starts one. isAnagram compares lengths, then counts letters up and down in a [26]int, which Go compares with == against its zero value.

package main

func groupAnagrams(strs []string) [][]string {
	groups := [][]string{}
next:
	for _, word := range strs {
		for i := range groups {
			if isAnagram(groups[i][0], word) {
				groups[i] = append(groups[i], word)
				continue next
			}
		}
		groups = append(groups, []string{word})
	}
	return groups
}

func isAnagram(a, b string) bool {
	if len(a) != len(b) {
		return false
	}
	var counts [26]int
	for i := 0; i < len(a); i++ {
		counts[a[i]-'a']++
		counts[b[i]-'a']--
	}
	return counts == [26]int{}
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

Every anagram sorts to the same bytes, so string(sorted) is the key of a map[string][]string. Go maps iterate in random order, so a separate order slice records each key when it first appears; the result is built from it, which also keeps the output the same from run to run. Words are appended in input order, so each group keeps it.

package main

import "slices"

func groupAnagrams(strs []string) [][]string {
	groups := make(map[string][]string)
	order := []string{}
	for _, word := range strs {
		b := []byte(word)
		slices.Sort(b)
		key := string(b)
		if _, ok := groups[key]; !ok {
			order = append(order, key)
		}
		groups[key] = append(groups[key], word)
	}
	result := make([][]string, 0, len(order))
	for _, key := range order {
		result = append(result, groups[key])
	}
	return result
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

In Go an array is a comparable value, so a [26]int of letter counts can be the map key as it is: no string building, no separators. Filling it is one pass over the word, which makes the whole function O(n·k). The order slice again fixes the group order.

package main

func groupAnagrams(strs []string) [][]string {
	groups := make(map[[26]int][]string)
	order := [][26]int{}
	for _, word := range strs {
		var key [26]int
		for i := 0; i < len(word); i++ {
			key[word[i]-'a']++
		}
		if _, ok := groups[key]; !ok {
			order = append(order, key)
		}
		groups[key] = append(groups[key], word)
	}
	result := make([][]string, 0, len(order))
	for _, key := range order {
		result = append(result, groups[key])
	}
	return result
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a List<List<string>> of groups. Find returns the first group whose first word is an anagram of the current one, or null, in which case the word starts a new group. IsAnagram checks the lengths, then counts letters up and down in an int[26]. The method returns string[][], so each list is copied out with ToArray.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static string[][] GroupAnagrams(string[] strs)
    {
        var groups = new List<List<string>>();
        foreach (var word in strs)
        {
            var group = groups.Find(g => IsAnagram(g[0], word));
            if (group != null) group.Add(word);
            else groups.Add(new List<string> { word });
        }
        return groups.Select(g => g.ToArray()).ToArray();
    }

    static bool IsAnagram(string a, string b)
    {
        if (a.Length != b.Length) return false;
        var counts = new int[26];
        for (int i = 0; i < a.Length; i++)
        {
            counts[a[i] - 'a']++;
            counts[b[i] - 'a']--;
        }
        return counts.All(c => c == 0);
    }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters: ToCharArray, Array.Sort and new string(chars) build the key of a Dictionary<string, List<string>>. TryGetValue finds the key's list in one lookup. A separate order list keeps the groups in the order their first word appeared, because a dictionary does not promise any order.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static string[][] GroupAnagrams(string[] strs)
    {
        var groups = new Dictionary<string, List<string>>();
        var order = new List<List<string>>();
        foreach (var word in strs)
        {
            var chars = word.ToCharArray();
            Array.Sort(chars);
            var key = new string(chars);
            if (!groups.TryGetValue(key, out var group))
            {
                group = new List<string>();
                groups[key] = group;
                order.Add(group);
            }
            group.Add(word);
        }
        return order.Select(g => g.ToArray()).ToArray();
    }
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count the letters in one pass instead of sorting. The counts go into a char[26], one character per letter, and new string(counts) makes a fixed-length key: each count has its own position, so counts of 1 and 11 never run into 11 and 1. A char holds up to 65,535, far more than any word here.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static string[][] GroupAnagrams(string[] strs)
    {
        var groups = new Dictionary<string, List<string>>();
        var order = new List<List<string>>();
        foreach (var word in strs)
        {
            var counts = new char[26];
            foreach (var c in word) counts[c - 'a']++;
            var key = new string(counts);
            if (!groups.TryGetValue(key, out var group))
            {
                group = new List<string>();
                groups[key] = group;
                order.Add(group);
            }
            group.Add(word);
        }
        return order.Select(g => g.ToArray()).ToArray();
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a vector<vector<string>> of groups and compare each word with the first word of every group so far; the word joins the first match or starts a new group. isAnagram checks the sizes, then counts letters up and down in an int[26]. Both helpers take const string&, so no word is copied for a comparison.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> groups;
        for (const string& word : strs) {
            bool placed = false;
            for (auto& group : groups) {
                if (isAnagram(group[0], word)) {
                    group.push_back(word);
                    placed = true;
                    break;
                }
            }
            if (!placed) groups.push_back({word});
        }
        return groups;
    }

    bool isAnagram(const string& a, const string& b) {
        if (a.size() != b.size()) return false;
        int counts[26] = {0};
        for (size_t i = 0; i < a.size(); i++) {
            counts[a[i] - 'a']++;
            counts[b[i] - 'a']--;
        }
        for (int c : counts) if (c != 0) return false;
        return true;
    }
};

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

Every anagram sorts to the same string, so a sorted copy of the word is the key. The map stores the group's position in result, not the group itself: try_emplace inserts the next index only when the key is new, and the word is appended to result[it->second]. That keeps the groups in the order their first word appeared and avoids copying them out of the map.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, int> index; // sorted letters -> position in result
        vector<vector<string>> result;
        for (const string& word : strs) {
            string key = word;
            sort(key.begin(), key.end());
            auto [it, inserted] = index.try_emplace(key, (int)result.size());
            if (inserted) result.emplace_back();
            result[it->second].push_back(word);
        }
        return result;
    }
};

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count the letters instead of sorting: a string key(26, 0) holds one count per letter as a character, filled in one pass over the word. The key has a fixed length and each count its own position, so counts of 1 and 11 never collide with 11 and 1. A char holds at least 127, more than the 20-letter limit needs.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, int> index; // letter counts -> position in result
        vector<vector<string>> result;
        for (const string& word : strs) {
            string key(26, 0);
            for (char c : word) key[c - 'a']++;
            auto [it, inserted] = index.try_emplace(key, (int)result.size());
            if (inserted) result.emplace_back();
            result[it->second].push_back(word);
        }
        return result;
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Give every word a group number. Remember the index of each group's first word in first, and walk those groups for each new word until is_anagram says yes, or open a new group. is_anagram compares the lengths, then counts letters up for one word and down for the other in an int[26]. A second pass knows every group's size, so each row is malloc'ed once and filled with copies of the words in input order.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static bool is_anagram(const char* a, const char* b) {
    size_t n = strlen(a);
    if (n != strlen(b)) return false;
    int counts[26] = {0};
    for (size_t i = 0; i < n; i++) {
        counts[a[i] - 'a']++;
        counts[b[i] - 'a']--;
    }
    for (int c = 0; c < 26; c++) {
        if (counts[c] != 0) return false;
    }
    return true;
}

static char* copy_word(const char* s) {
    size_t n = strlen(s) + 1;
    char* out = malloc(n);
    memcpy(out, s, n);
    return out;
}

/**
 * Note: the returned arrays, their strings and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    int* first = malloc(strsSize * sizeof *first);   // first word of each group
    int* groupOf = malloc(strsSize * sizeof *groupOf);
    int groupCount = 0;
    for (int i = 0; i < strsSize; i++) {
        int g = 0;
        while (g < groupCount && !is_anagram(strs[first[g]], strs[i])) g++;
        if (g == groupCount) first[groupCount++] = i;
        groupOf[i] = g;
    }

    int* sizes = calloc(groupCount, sizeof *sizes);
    for (int i = 0; i < strsSize; i++) sizes[groupOf[i]]++;
    char*** result = malloc(groupCount * sizeof *result);
    int* filled = calloc(groupCount, sizeof *filled);
    for (int g = 0; g < groupCount; g++) result[g] = malloc(sizes[g] * sizeof *result[g]);
    for (int i = 0; i < strsSize; i++) {
        int g = groupOf[i];
        result[g][filled[g]++] = copy_word(strs[i]);
    }

    free(first);
    free(groupOf);
    free(filled);
    *returnSize = groupCount;
    *returnColumnSizes = sizes;
    return result;
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

Every anagram sorts to the same letters, so a malloc'ed copy of the word run through qsort is its group's key. C has no hash map, so the keys go into an open-addressing table at least twice the input's size, hashed with FNV-1a and probed linearly; each slot holds the key and its group number. The empty word gets a one-byte key, just the '\0', which is still a real key and not an empty slot.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int cmp_char(const void* a, const void* b) {
    return *(const char*)a - *(const char*)b;
}

static unsigned hash_str(const char* s) {
    unsigned h = 2166136261u;   // FNV-1a
    for (; *s; s++) h = (h ^ (unsigned char)*s) * 16777619u;
    return h;
}

static char* copy_word(const char* s) {
    size_t n = strlen(s) + 1;
    char* out = malloc(n);
    memcpy(out, s, n);
    return out;
}

/**
 * Note: the returned arrays, their strings and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    unsigned capacity = 1;
    while (capacity < 2u * (unsigned)strsSize) capacity <<= 1;
    char** keys = calloc(capacity, sizeof *keys);   // NULL marks an empty slot
    int* slotGroup = malloc(capacity * sizeof *slotGroup);
    int* groupOf = malloc(strsSize * sizeof *groupOf);
    int groupCount = 0;

    for (int i = 0; i < strsSize; i++) {
        char* key = copy_word(strs[i]);
        qsort(key, strlen(key), 1, cmp_char);
        unsigned slot = hash_str(key) & (capacity - 1);
        while (keys[slot] && strcmp(keys[slot], key) != 0) slot = (slot + 1) & (capacity - 1);
        if (keys[slot]) {
            free(key);
        } else {
            keys[slot] = key;
            slotGroup[slot] = groupCount++;
        }
        groupOf[i] = slotGroup[slot];
    }

    int* sizes = calloc(groupCount, sizeof *sizes);
    for (int i = 0; i < strsSize; i++) sizes[groupOf[i]]++;
    char*** result = malloc(groupCount * sizeof *result);
    int* filled = calloc(groupCount, sizeof *filled);
    for (int g = 0; g < groupCount; g++) result[g] = malloc(sizes[g] * sizeof *result[g]);
    for (int i = 0; i < strsSize; i++) {
        int g = groupOf[i];
        result[g][filled[g]++] = copy_word(strs[i]);
    }

    for (unsigned s = 0; s < capacity; s++) free(keys[s]);
    free(keys);
    free(slotGroup);
    free(groupOf);
    free(filled);
    *returnSize = groupCount;
    *returnColumnSizes = sizes;
    return result;
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count the letters instead of sorting: one pass fills 26 unsigned char counts, and those 26 bytes are the key. Every key has the same fixed length, so the table stores them side by side in one block and compares them with memcmp; a count of 1 then 11 sits in different bytes from 11 then 1, so they never collide. Building the key is linear in the word length.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static char* copy_word(const char* s) {
    size_t n = strlen(s) + 1;
    char* out = malloc(n);
    memcpy(out, s, n);
    return out;
}

/**
 * Note: the returned arrays, their strings and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    unsigned capacity = 1;
    while (capacity < 2u * (unsigned)strsSize) capacity <<= 1;
    unsigned char* keys = malloc(capacity * 26);   // 26 counts per slot
    bool* used = calloc(capacity, sizeof *used);
    int* slotGroup = malloc(capacity * sizeof *slotGroup);
    int* groupOf = malloc(strsSize * sizeof *groupOf);
    int groupCount = 0;

    for (int i = 0; i < strsSize; i++) {
        unsigned char counts[26] = {0};
        for (const char* p = strs[i]; *p; p++) counts[*p - 'a']++;
        unsigned h = 2166136261u;   // FNV-1a over the 26 bytes
        for (int c = 0; c < 26; c++) h = (h ^ counts[c]) * 16777619u;
        unsigned slot = h & (capacity - 1);
        while (used[slot] && memcmp(keys + slot * 26, counts, 26) != 0) slot = (slot + 1) & (capacity - 1);
        if (!used[slot]) {
            used[slot] = true;
            memcpy(keys + slot * 26, counts, 26);
            slotGroup[slot] = groupCount++;
        }
        groupOf[i] = slotGroup[slot];
    }

    int* sizes = calloc(groupCount, sizeof *sizes);
    for (int i = 0; i < strsSize; i++) sizes[groupOf[i]]++;
    char*** result = malloc(groupCount * sizeof *result);
    int* filled = calloc(groupCount, sizeof *filled);
    for (int g = 0; g < groupCount; g++) result[g] = malloc(sizes[g] * sizeof *result[g]);
    for (int i = 0; i < strsSize; i++) {
        int g = groupOf[i];
        result[g][filled[g]++] = copy_word(strs[i]);
    }

    free(keys);
    free(used);
    free(slotGroup);
    free(groupOf);
    free(filled);
    *returnSize = groupCount;
    *returnColumnSizes = sizes;
    return result;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a MutableList<MutableList<String>> of groups. For each word, firstOrNull finds the first group whose first word is an anagram of it; the word joins that group or starts a new one. isAnagram compares the lengths, then counts letters up and down in an IntArray(26). The signature returns Array<Array<String>>, so the lists are converted with toTypedArray() at the end.

class Solution {
    fun groupAnagrams(strs: Array<String>): Array<Array<String>> {
        val groups = mutableListOf<MutableList<String>>()
        for (word in strs) {
            val group = groups.firstOrNull { isAnagram(it[0], word) }
            if (group != null) group.add(word) else groups.add(mutableListOf(word))
        }
        return groups.map { it.toTypedArray() }.toTypedArray()
    }

    private fun isAnagram(a: String, b: String): Boolean {
        if (a.length != b.length) return false
        val counts = IntArray(26)
        for (i in a.indices) {
            counts[a[i] - 'a']++
            counts[b[i] - 'a']--
        }
        return counts.all { it == 0 }
    }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters, so String(word.toCharArray().apply { sort() }) is a key the whole group shares. groupBy builds a LinkedHashMap: the groups come out in the order their first word appeared, and each list keeps the input order.

class Solution {
    fun groupAnagrams(strs: Array<String>): Array<Array<String>> =
        strs.groupBy { String(it.toCharArray().apply { sort() }) }
            .values
            .map { it.toTypedArray() }
            .toTypedArray()
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count instead of sorting, which is linear in the word length. The counts go into a CharArray(26), one character per letter at a fixed position, and String(counts) turns them into a key that compares by value; counts of 1 and 11 sit in different positions from 11 and 1. getOrPut fetches the key's list or creates it.

class Solution {
    fun groupAnagrams(strs: Array<String>): Array<Array<String>> {
        val groups = LinkedHashMap<String, MutableList<String>>()
        for (word in strs) {
            val counts = CharArray(26)
            for (ch in word) counts[ch - 'a']++
            groups.getOrPut(String(counts)) { mutableListOf() }.add(word)
        }
        return groups.values.map { it.toTypedArray() }.toTypedArray()
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a Vec<Vec<String>> of groups. For each word, position finds the first group whose first word is an anagram of it; the word is moved into that group or starts a new one, so no string is cloned. is_anagram compares the byte lengths, then counts letters up and down in an [i32; 26].

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut groups: Vec<Vec<String>> = Vec::new();
        for word in strs {
            match groups.iter().position(|g| Self::is_anagram(&g[0], &word)) {
                Some(g) => groups[g].push(word),
                None => groups.push(vec![word]),
            }
        }
        groups
    }

    fn is_anagram(a: &str, b: &str) -> bool {
        if a.len() != b.len() {
            return false;
        }
        let mut counts = [0i32; 26];
        for (x, y) in a.bytes().zip(b.bytes()) {
            counts[(x - b'a') as usize] += 1;
            counts[(y - b'a') as usize] -= 1;
        }
        counts.iter().all(|&c| c == 0)
    }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters. The words are ASCII, so the key is the word's bytes in a Vec<u8> after sort_unstable. The map stores a group index rather than the group: entry(key).or_insert_with pushes a new empty group the first time a key is seen, so the groups stay in the order their first word appeared and come back without draining a map.

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut index: HashMap<Vec<u8>, usize> = HashMap::with_capacity(strs.len());
        let mut groups: Vec<Vec<String>> = Vec::new();
        for word in strs {
            let mut key = word.as_bytes().to_vec();
            key.sort_unstable();
            let g = *index.entry(key).or_insert_with(|| {
                groups.push(Vec::new());
                groups.len() - 1
            });
            groups[g].push(word);
        }
        groups
    }
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count instead of sorting, which is linear in the word length. A [u8; 26] array implements Hash and Eq element by element, so it is the key as it is: no string to build, and counts of 1 and 11 never look like 11 and 1. Words hold at most 20 letters, so a u8 per count is plenty.

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut index: HashMap<[u8; 26], usize> = HashMap::with_capacity(strs.len());
        let mut groups: Vec<Vec<String>> = Vec::new();
        for word in strs {
            let mut counts = [0u8; 26];
            for b in word.bytes() {
                counts[(b - b'a') as usize] += 1;
            }
            let g = *index.entry(counts).or_insert_with(|| {
                groups.push(Vec::new());
                groups.len() - 1
            });
            groups[g].push(word);
        }
        groups
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep an array of groups. For each word, firstIndex(where:) finds the first group whose first word is an anagram of it; the word joins that group or starts a new one. isAnagram works on the utf8 views: it compares the byte counts, then counts letters up for one word and down for the other in a 26-slot array.

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var groups: [[String]] = []
        for word in strs {
            if let g = groups.firstIndex(where: { isAnagram($0[0], word) }) {
                groups[g].append(word)
            } else {
                groups.append([word])
            }
        }
        return groups
    }

    private func isAnagram(_ a: String, _ b: String) -> Bool {
        if a.utf8.count != b.utf8.count { return false }
        var counts = [Int](repeating: 0, count: 26)
        for c in a.utf8 { counts[Int(c) - 97] += 1 }
        for c in b.utf8 { counts[Int(c) - 97] -= 1 }
        return counts.allSatisfy { $0 == 0 }
    }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters, so String(word.sorted()) is a key the whole group shares. Swift dictionaries have no order, so the dictionary maps each key to a group index in a separate [[String]]: the groups stay in the order their first word appeared, and appending keeps each group in input order.

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var index: [String: Int] = [:]
        var groups: [[String]] = []
        for word in strs {
            let key = String(word.sorted())
            if let g = index[key] {
                groups[g].append(word)
            } else {
                index[key] = groups.count
                groups.append([word])
            }
        }
        return groups
    }
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count instead of sorting, which is linear in the word length. Arrays of a Hashable element are Hashable themselves, so the 26 counts in an [Int] are the key as they are, compared element by element: counts of 1 and 11 never look like 11 and 1.

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var index: [[Int]: Int] = [:]
        var groups: [[String]] = []
        for word in strs {
            var counts = [Int](repeating: 0, count: 26)
            for c in word.utf8 { counts[Int(c) - 97] += 1 }
            if let g = index[counts] {
                groups[g].append(word)
            } else {
                index[counts] = groups.count
                groups.append([word])
            }
        }
        return groups
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a list of groups. For each word, walk the groups by index and compare the word with each group's first word; append it to the first match with $groups[$g][] = $word, or start a new group. isAnagram compares the lengths, then the letter counts from count_chars($s, 1), which maps each byte that occurs to how often it occurs.

<?php

class Solution {
    /**
     * @param string[] $strs
     * @return string[][]
     */
    function groupAnagrams(array $strs): array {
        $groups = [];
        foreach ($strs as $word) {
            $found = false;
            $count = count($groups);
            for ($g = 0; $g < $count; $g++) {
                if ($this->isAnagram($groups[$g][0], $word)) {
                    $groups[$g][] = $word;
                    $found = true;
                    break;
                }
            }
            if (!$found) {
                $groups[] = [$word];
            }
        }
        return $groups;
    }

    private function isAnagram(string $a, string $b): bool {
        return strlen($a) === strlen($b) && count_chars($a, 1) == count_chars($b, 1);
    }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters: str_split, sort and implode build that key, and $groups[$key][] = $word creates the group or appends to it. PHP arrays keep insertion order, so the groups come out in first-seen order and each keeps the input order; array_values drops the string keys to return a list.

<?php

class Solution {
    /**
     * @param string[] $strs
     * @return string[][]
     */
    function groupAnagrams(array $strs): array {
        $groups = [];
        foreach ($strs as $word) {
            $letters = str_split($word);
            sort($letters);
            $groups[implode('', $letters)][] = $word;
        }
        return array_values($groups);
    }
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count instead of sorting, which is linear in the word length. The 26 counts are joined with commas, so a count of 1 then 11 reads 1,11 and never collides with 11,1. The key always contains commas, so PHP never mistakes it for an integer key.

<?php

class Solution {
    /**
     * @param string[] $strs
     * @return string[][]
     */
    function groupAnagrams(array $strs): array {
        $groups = [];
        foreach ($strs as $word) {
            $counts = array_fill(0, 26, 0);
            $n = strlen($word);
            for ($i = 0; $i < $n; $i++) {
                $counts[ord($word[$i]) - 97]++;
            }
            $groups[implode(',', $counts)][] = $word;
        }
        return array_values($groups);
    }
}

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep a list of groups. For each word, indexWhere finds the first group whose first word is an anagram of it; the word joins that group or starts a new one. _isAnagram compares the lengths, then counts the codeUnits up for one word and down for the other in a 26-slot list.

class Solution {
  List<List<String>> groupAnagrams(List<String> strs) {
    final groups = <List<String>>[];
    for (final word in strs) {
      final g = groups.indexWhere((group) => _isAnagram(group[0], word));
      if (g >= 0) {
        groups[g].add(word);
      } else {
        groups.add([word]);
      }
    }
    return groups;
  }

  bool _isAnagram(String a, String b) {
    if (a.length != b.length) return false;
    final counts = List<int>.filled(26, 0);
    for (var i = 0; i < a.length; i++) {
      counts[a.codeUnitAt(i) - 97]++;
      counts[b.codeUnitAt(i) - 97]--;
    }
    return counts.every((c) => c == 0);
  }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters: (word.split('')..sort()).join() builds that key with a cascade, and putIfAbsent fetches the key's list or creates it. A map literal is a LinkedHashMap, so values lists the groups in the order their first word appeared, each in input order.

class Solution {
  List<List<String>> groupAnagrams(List<String> strs) {
    final groups = <String, List<String>>{};
    for (final word in strs) {
      final key = (word.split('')..sort()).join();
      groups.putIfAbsent(key, () => []).add(word);
    }
    return groups.values.toList();
  }
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count instead of sorting, which is linear in the word length. A List<int> compares by identity, so it cannot be the key; counts.join(',') turns the 26 counts into a string, and the commas keep a count of 1 then 11 apart from 11 then 1.

class Solution {
  List<List<String>> groupAnagrams(List<String> strs) {
    final groups = <String, List<String>>{};
    for (final word in strs) {
      final counts = List<int>.filled(26, 0);
      for (final unit in word.codeUnits) {
        counts[unit - 97]++;
      }
      groups.putIfAbsent(counts.join(','), () => []).add(word);
    }
    return groups.values.toList();
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: compare each word with every group so far

O(n²·k) time · O(n·k) space

Keep an ArrayBuffer of groups. For each word, find returns the first group whose first word is an anagram of it, and the match appends the word to it or starts a new group. isAnagram compares the lengths, then counts letters up and down in an Array[Int] with a while loop.

import scala.collection.mutable.ArrayBuffer

object Solution {
  def groupAnagrams(strs: Array[String]): Array[Array[String]] = {
    val groups = ArrayBuffer.empty[ArrayBuffer[String]]
    for (word <- strs) {
      groups.find(g => isAnagram(g(0), word)) match {
        case Some(group) => group += word
        case None        => groups += ArrayBuffer(word)
      }
    }
    groups.map(_.toArray).toArray
  }

  private def isAnagram(a: String, b: String): Boolean = {
    if (a.length != b.length) return false
    val counts = new Array[Int](26)
    var i = 0
    while (i < a.length) {
      counts(a(i) - 'a') += 1
      counts(b(i) - 'a') -= 1
      i += 1
    }
    counts.forall(_ == 0)
  }
}

2 · Hash map keyed by the sorted word

O(n·k log k) time · O(n·k) space

All anagrams sort to the same letters, and word.sorted returns them as a String. getOrElseUpdate on a mutable.LinkedHashMap fetches the key's buffer or creates it, so the groups stay in the order their first word appeared and each keeps the input order.

import scala.collection.mutable

object Solution {
  def groupAnagrams(strs: Array[String]): Array[Array[String]] = {
    val groups = mutable.LinkedHashMap.empty[String, mutable.ArrayBuffer[String]]
    for (word <- strs) groups.getOrElseUpdate(word.sorted, mutable.ArrayBuffer.empty) += word
    groups.values.map(_.toArray).toArray
  }
}

3 · Hash map keyed by the 26 letter counts

O(n·k) time · O(n·k) space

recommended

Count instead of sorting, which is linear in the word length. An Array[Int] compares by reference, so counts.toSeq wraps the 26 counts in an immutable ArraySeq that compares and hashes by its elements: counts of 1 and 11 never look like 11 and 1.

import scala.collection.mutable

object Solution {
  def groupAnagrams(strs: Array[String]): Array[Array[String]] = {
    val groups = mutable.LinkedHashMap.empty[Seq[Int], mutable.ArrayBuffer[String]]
    for (word <- strs) {
      val counts = new Array[Int](26)
      for (ch <- word) counts(ch - 'a') += 1
      groups.getOrElseUpdate(counts.toSeq, mutable.ArrayBuffer.empty) += word
    }
    groups.values.map(_.toArray).toArray
  }
}

FAQ for Ruby

Why Hash.new with a block and not Hash.new([])?

Hash.new([]) returns the same array object as the default for every missing key and never stores it, so groups[key] << word pushes every word into that one shared array and the hash stays empty. The block form, Hash.new { |h, k| h[k] = [] }, creates a fresh array per key and stores it.

Is it safe to use an array as a hash key?

Yes, as long as you do not mutate it afterwards. counts is a fresh array for each word and is never changed once it is a key. If you did change a key array, its hash would no longer match and you would need groups.rehash.

Is sort.join faster than counting in Ruby?

For short words, usually yes: chars.sort.join runs mostly in C, while the counting loop runs a Ruby block per byte. Counting only wins on long words, where O(k) beats O(k log k). each_byte is the cheapest way to walk the letters, because it does not build a string per character the way each_char does.

Can I use each_with_object instead?

Yes: strs.each_with_object(Hash.new { |h, k| h[k] = [] }) { |w, h| h[w.chars.sort.join] << w }.values builds the same groups. group_by says the same thing more directly, so the sorted-key solution uses it.

What does chars.tally return?

tally counts equal elements and returns a hash such as {"a"=>2, "b"=>1}. Two hashes compare equal with == when they hold the same pairs, in any order, which is exactly the anagram test. It was added in Ruby 2.7.

Keep going

Top K Frequent Elements27 / 40 · Hash map · Medium

Try Group Anagrams in Python (Group Anagrams in Python), JavaScript (Group Anagrams in JavaScript), TypeScript (Group Anagrams in TypeScript), Java (Group Anagrams in Java), Go (Group Anagrams in Go), C# (Group Anagrams in C#), C++ (Group Anagrams in C++), C (Group Anagrams in C), Kotlin (Group Anagrams in Kotlin), Rust (Group Anagrams in Rust), Swift (Group Anagrams in Swift), PHP (Group Anagrams in PHP), Dart (Group Anagrams in Dart) or Scala (Group Anagrams in Scala) instead.

group_anagrams.rb

Ruby 4.0

Not run yet

+ 7 hidden

Input

strs = ["race", "care", "arc", "acre", "car", "cat"]

Expected

[["race", "care", "acre"], ["arc", "car"], ["cat"]]

race, care and acre use the same four letters, arc and car the same three. cat has no partner, so it is a group of one. Inside each group the words keep their input order.