Skip to main content

49. Group Anagrams

medium

Cluster strings into anagram groups. Tests hash-map intuition plus the key insight that a sorted version of an anagram is the same for every member of its group.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Constraints

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

Examples

Example 1

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

Example 2

Input
strs = [""]
Output
[[""]]

Example 3

Input
strs = ["a"]
Output
[["a"]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two strings are anagrams iff they share a canonical form.

Hint 2

What canonical form? Sorted characters works: sort('eat') = 'aet' = sort('tea') = sort('ate').

Hint 3

Walk the input. For each string, compute its key (sorted chars or a 26-element frequency tuple). Append the original to map[key]. Return map.values().

Solution approach

Reveal approach

Hash map from canonical key to list of strings. For each input string, build a key — either the sorted character string ('eat' -> 'aet') or a count-of-each-letter tuple — and append the original string to map[key]. The first approach costs O(L log L) per string (for sorting); the second is O(L) where L is the string length. Return the map's values when done. Group order does not matter per the spec.

Complexity

Time
O(n * L log L)
Space
O(n * L)

Related patterns

  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Uber
  • Bloomberg

More Strings practice problems

See all Strings problems →