Skip to main content

49. Group Anagrams

medium

Group anagrams together from a list of strings. The right key is the entire problem — sorted-letters or letter-count tuple — and that key is what turns this from an O(n^2 * L) pair-check into an O(n * L) hash grouping.

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 their sorted character sequences are identical. So sorted(s) is a valid grouping key.

Hint 2

Hash map: key = sorted(s), value = list of original strings sharing that key. Group, then return the values.

Hint 3

For lowercase-only input, a length-26 count tuple is a cheaper key than sorting — O(L) per string instead of O(L log L).

Solution approach

Reveal approach

Hash map of key -> list of strings. For each string s, compute a canonical key — either ''.join(sorted(s)) (clear and short) or a tuple of 26 character counts (faster: O(L) instead of O(L log L)). Append s to the list at map[key]. After the loop, return list(map.values()). The tuple-key version is provably faster for long strings but the sorted-key version is what most candidates write — both are accepted. O(n * L) with the count-tuple key, O(n * L * log L) with the sort key.

Complexity

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

Related patterns

  • hash-table
  • string
  • sorting
  • counting

Related problems

Asked at

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

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Uber

More Hash Tables practice problems

See all Hash Tables problems →