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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Group Anagrams and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →