DSAPrep
MediumArrays & Hashing

Group Anagrams

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 of each other. The strings "ate", "eat", and "tea" are anagrams of 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.
View original on LeetCode ↗

Anagrams share the same multiset of letters, so if we can turn each string into a canonical “signature” that only depends on letter counts, then strings with the same signature belong in the same group. A hash map from signature to group does the rest in one pass.

Sorted-String Key

Time O(n · k log k)Space O(n · k)

Sort the letters of each string to get a canonical form — anagrams sort to the same string. Use that sorted string as a hash map key.

from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            groups[key].append(s)
        return list(groups.values())

Works, but sorting every one of the n strings costs O(k log k) each (k = max string length), for O(n · k log k) total — more work than necessary just to build a grouping key.

Character-Count Key

OptimalTime O(n · k)Space O(n · k)

Instead of sorting, count the occurrences of each of the 26 letters directly. Two strings are anagrams exactly when their count arrays match, so a tuple of counts makes an equally valid — and cheaper to compute — hash map key.

from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        groups = defaultdict(list)
        for s in strs:
            counts = [0] * 26
            for ch in s:
                counts[ord(ch) - ord('a')] += 1
            groups[tuple(counts)].append(s)
        return list(groups.values())

Tracing strs = ["eat", "tea", "tan", "ate"] (key shown as letter-count pairs in alphabetical order, e.g. a1e1t1, rather than the raw 26-length tuple):

eat
0
tea
1
tan
2
ate
3
string = eat

Hash Map

a1e1t1 → eat
1 / 4
resultcurrent

eat has counts a1 e1 t1. New key — start a new group.

Correctness: two strings produce the same count tuple if and only if they contain the same letters the same number of times — which is precisely the definition of anagram. Grouping by that key therefore groups exactly the anagrams together, regardless of letter order.

Complexity: building each string’s count array is O(k) (26 fixed increments spread over k characters), done for all n strings — O(n · k) time, better than sorting’s O(n · k log k). Every character across every string ends up stored once in the output groups — O(n · k) space.