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 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 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

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →