Domain 2MediumCORE

Group Anagrams

We are given an array of strings strs. The goal is to group all words that are anagrams into the same sub-list. An anagram means two strings contain exactly the same characters with the exact same frequencies, regardless of order (e.g., 'eat' and 'tea').

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#String

49. Group Anagrams

Model: qwen3.5:9b
Topics: Hash Table,String
FAANG asked: 1
Acceptance rate: 59.7%


Problem Breakdown

We are given an array of strings strs. The goal is to group all words that are anagrams into the same sub-list. An anagram means two strings contain exactly the same characters with the exact same frequencies, regardless of order (e.g., “eat” and “tea”).

Inputs: A list of lowercase English letter strings (1 <= strs.length). Outputs: A 2D array where each inner array contains a group of anagrams. The order of groups or words within groups does not matter. Constraints & Edge Cases:

  • Strings can be empty (length 0). An empty string is its own canonical key "". If multiple empty strings exist, they share this key and are grouped into the same list in the output.
  • Input length up to 10410^4, individual word length up to 100100. This suggests we need better than quadratic time complexity relative to the number of words.

Intuition

A brute-force approach would be to compare every pair of strings in the array to check if they are anagrams (sorting each and comparing, or counting characters). That results in O(N2⋅L)O(N^2 \cdot L) where NN is the number of words and LL is string length. With N=104N=10^4, this will time out.

The key insight for grouping problems like this is finding a canonical representation (a unique identifier) that remains constant regardless of character order. If we sort the characters in every word, all anagrams will produce the exact same sorted string. For example: "eat", "tea", and "ate" all become "aet". We can use a Hash Map where the key is this canonical representation (the sorted string) and the value is a list of original words that match it. This reduces us to iterating through the array once, O(N⋅L)O(N \cdot L) or O(N⋅Llog⁡L)O(N \cdot L \log L) depending on how we compute the key.

Approach

  1. Initialize an empty dictionary (hash map).
  2. Iterate over each string s in the input list strs.
  3. Compute a unique key for s. The most Pythonic way is to sort its characters: key = "".join(sorted(s)). Alternatively, we could use a frequency tuple of counts ‘a’-‘z’, but sorting handles any character set naturally and leverages optimized C internals in Python.
  4. Use the dictionary’s .get() method or initialize logic to append s to the list associated with that key. If the key doesn’t exist, create an empty list first.
  5. After processing all strings, return the values of the dictionary as a list of lists.

Complexity Analysis

  • Time: O(N⋅Llog⁡L)O(N \cdot L \log L) where NN is number of words and LL is max word length. Sorting each string takes O(Llog⁡L)O(L \log L). We do this for every word (NN times). Dictionary operations are average O(1)O(1).
  • Space: O(N⋅L)O(N \cdot L) to store the output groups plus the dictionary overhead (keys and lists of strings).

Solution

from typing import List

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    # Dictionary mapping sorted string key -> list of original anagram words
    anagram_map = {}
    
    for word in strs:
        # Create a canonical key by sorting characters. 
        # "eat" -> ['a', 'e', 't'] -> join to "aet". All anagrams share this key.
        sorted_key = "".join(sorted(word))
        
        if sorted_key not in anagram_map:
            anagram_map[sorted_key] = []
            
        anagram_map[sorted_key].append(word)
    
    # Return the grouped lists as a list of values from our map
    return list(anagram_map.values())

# Example usage (uncomment for testing):
# print(groupAnagrams(["eat","tea","tan","ate","nat","bat"])) 

Edge Cases Handled

  • Empty strings: If strs contains "", sorting it results in an empty key. The code creates a group [ ""]. This matches Example 2 behavior correctly. Multiple empty strings will share this single key and be grouped together.
  • Single element input: Loop runs once, map has one entry with length 1 list. Returns correct structure.
  • No Anagrams (all unique): Each word generates a unique sorted key. Map contains NN entries each with size 1. Correctly returns all words in separate groups.
  • All same anagram: All generate the same key, map has one entry containing all input strings.