TIC
The Interns Company

Group Anagrams

MediumAcceptance: 63.7%
ArrayHash TableStringSorting

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints:

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

Input Format:

  • An array of strings strs

Output Format:

  • Return a list of grouped anagrams (a list of lists)

Examples:

Example 1:

Input:

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

Output:

[["bat"],["nat","tan"],["ate","eat","tea"]]

Explanation:

The strings can be grouped into anagrams: ['eat', 'tea', 'ate'] (all anagrams of each other), ['tan', 'nat'] (anagrams of each other), and ['bat'] (no anagrams).

Example 2:

Input:

strs = [""]

Output:

[[""]]

Explanation:

There is only one string, so it is grouped by itself.

Example 3:

Input:

strs = ["a"]

Output:

[["a"]]

Explanation:

There is only one string, so it is grouped by itself.

Solutions

Sorted String as Key

Time: O(n * k log k)
Space: O(n * k)

Sort each string to get a canonical form, then use this sorted string as a key in a hash map to group anagrams.

Character Count as Key

Time: O(n * k)
Space: O(n * k)

Use a character count as a key for the hash map. Since there are only 26 lowercase letters, we can create a count array or string representation of the character frequencies.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize an empty hash map
  2. Process 'eat': Sort to get 'aet', add to map: {'aet': ['eat']}
  3. Process 'tea': Sort to get 'aet', add to map: {'aet': ['eat', 'tea']}
  4. Process 'tan': Sort to get 'ant', add to map: {'aet': ['eat', 'tea'], 'ant': ['tan']}
  5. Process 'ate': Sort to get 'aet', add to map: {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
  6. Process 'nat': Sort to get 'ant', add to map: {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}
  7. Process 'bat': Sort to get 'abt', add to map: {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}
  8. Return the values from the map: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Hints

Hint 1
Two strings are anagrams if and only if they have the same characters with the same frequencies.
Hint 2
How can we represent a string in a way that anagrams would have the same representation?
Hint 3
Consider using a sorted string or a character count as a key in a hash table.

Video Tutorial

Group Anagrams - Efficient Approach

YouTube•Learn the Group Anagrams solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize how strings are sorted and grouped by their canonical forms in a hash table.

Key visualization elements:

  • current string
  • sorted form
  • hash table state

Similar Questions

Valid Anagram

Easy

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Asked By

AmazonMicrosoftFacebookBloombergUberAppleGoogle

Implementation Notes

This problem introduces the concept of using a canonical representation for strings, which is a common technique for identifying anagrams. The sorted string approach is more intuitive, but the character count approach offers better time complexity when the strings are long.