Group Anagrams

LeetCode 49: Group Anagrams Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a Hash Map to group strings by using their sorted character sequence as a unique key (canonical form).

The LeetCode 49 problem, "Group Anagrams," asks us to process an array of strings and categorize them into groups where every string in a group is an anagram of the others. An anagram is defined as a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. The order of the output groups does not matter.

This is a classic interview question that tests your ability to identify shared properties between data objects and efficient hashing strategies.

Brute Force Approach for Group Anagrams

The naive approach involves iterating through the array and, for each string, checking it against every other string to see if they are anagrams. If a match is found, they are grouped together. To prevent processing the same string twice, we would need to maintain a visited array.

Naive Algorithm Logic:

1. Initialize a list of groups.
2. Iterate through the input array with index i.
3. If strs[i] has been visited, skip it.
4. Create a new group containing strs[i].
5. Iterate through the rest of the array with index j.
6. Check if strs[j] is an anagram of strs[i] (often by sorting both temp strings).
7. If yes, add strs[j] to the group and mark strs[j] as visited.

Why this fails: The time complexity of this approach is roughly $O(N^2 \cdot K \log K)$, where $N$ is the number of strings and $K$ is the maximum length of a string.

• The nested loops result in $O(N^2)$ comparisons.
• The anagram check (usually via sorting) takes $O(K \log K)$.

Given the constraint $N \le 10^4$, $N^2$ results in $10^8$ operations before even considering the string length factor. This will almost certainly result in a Time Limit Exceeded (TLE) error on modern coding platforms.

Algorithm Strategy: String Manipulation Patterns

We will implement the solution using a Hash Map (or Dictionary) to group the data in a single pass ($O(N)$).

1. Data Structure Initialization: Create a Hash Map where:

   • The Key is a String (the sorted version of the word).
   • The Value is a List of Strings (the group of anagrams).

2. Iteration: Loop through every string in the input array strs.

3. Canonical Key Generation: For the current string, generate its key by sorting its characters. This enforces the constraint that order does not matter, only character composition.

4. Grouping:

   • Check if this sorted key exists in the Hash Map.
   • If not, initialize a new entry with this key and an empty list.
   • Append the original (unsorted) string to the list associated with the sorted key.

5. Output: Extract all the lists (values) from the Hash Map and return them.

This strategy effectively reduces the comparison complexity from checking every pair ($N^2$) to checking against a hash table ($O(1)$ average), resulting in a linear dependency on $N$.

Execution Flow

Let's trace the algorithm with the input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"].

1. Initialize Map: groups = {}

2. Process "eat":

   • Sort "eat" $\rightarrow$ Key: "aet"
   • "aet" not in map. Create entry.
   • groups state: {"aet": ["eat"]}

3. Process "tea":

   • Sort "tea" $\rightarrow$ Key: "aet"
   • "aet" exists. Append "tea".
   • groups state: {"aet": ["eat", "tea"]}

4. Process "tan":

   • Sort "tan" $\rightarrow$ Key: "ant"
   • "ant" not in map. Create entry.
   • groups state: {"aet": ["eat", "tea"], "ant": ["tan"]}

5. Process "ate":

   • Sort "ate" $\rightarrow$ Key: "aet"
   • "aet" exists. Append "ate".
   • groups state: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}

6. Process "nat":

   • Sort "nat" $\rightarrow$ Key: "ant"
   • "ant" exists. Append "nat".
   • groups state: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}

7. Process "bat":

   • Sort "bat" $\rightarrow$ Key: "abt"
   • "abt" not in map. Create entry.
   • groups state: {"aet": [...], "ant": [...], "abt": ["bat"]}

8. Return: Collect values [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Proof of Correctness

The correctness relies on the fundamental theorem of anagrams: Two strings are anagrams if and only if they contain the exact same characters with the exact same frequencies.

By sorting the characters of a string, we produce a standardized sequence. If string $A$ and string $B$ are anagrams, their sorted versions $A_{sorted}$ and $B_{sorted}$ must be identical because sorting is deterministic and depends solely on character composition. Conversely, if $A$ and $B$ are not anagrams, they differ in character composition, implying $A_{sorted} \neq B_{sorted}$.

Therefore, the sorted string serves as a perfect hash key that collides strictly for anagrams and remains unique for non-anagrams.

Pattern Reuse Notes

The "Canonical Representation" pattern used here is highly versatile.

• LeetCode 242: Valid Anagram: This is the simplified version of Group Anagrams. Instead of grouping many strings, you simply compare two. The logic is identical: Sort both and compare, or use a frequency counter array.
• Isomorphic Strings: Similar to anagrams, this requires mapping characters to a canonical form (e.g., "paper" and "title" both map to a pattern like 0,1,0,2,3) to check for structural equality.

Reference Implementation

C++ Solution for LeetCode 49

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10    vector<vector<string>> groupAnagrams(vector<string>& strs) {
11        // Map to store sorted string -> list of original strings
12        unordered_map<string, vector<string>> groups;
13        
14        for (const string& s : strs) {
15            string key = s;
16            // Sort the string to create the canonical key
17            sort(key.begin(), key.end());
18            
19            // Add the original string to the corresponding group
20            groups[key].push_back(s);
21        }
22        
23        // Extract the grouped anagrams from the map
24        vector<vector<string>> result;
25        for (auto& entry : groups) {
26            result.push_back(entry.second);
27        }
28        
29        return result;
30    }
31};

Java Solution for LeetCode 49

1import java.util.*;
2
3class Solution {
4    public List<List<String>> groupAnagrams(String[] strs) {
5        if (strs == null || strs.length == 0) {
6            return new ArrayList<>();
7        }
8        
9        // Map to store sorted string -> list of original strings
10        Map<String, List<String>> map = new HashMap<>();
11        
12        for (String s : strs) {
13            // Convert to char array to sort
14            char[] characters = s.toCharArray();
15            Arrays.sort(characters);
16            
17            // Create the canonical key
18            String key = new String(characters);
19            
20            // Add to map, initializing list if key doesn't exist
21            if (!map.containsKey(key)) {
22                map.put(key, new ArrayList<>());
23            }
24            map.get(key).add(s);
25        }
26        
27        // Return only the values (the lists of grouped anagrams)
28        return new ArrayList<>(map.values());
29    }
30}

Python Solution for LeetCode 49

1from collections import defaultdict
2
3class Solution:
4    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
5        # Defaultdict avoids checking if key exists explicitly
6        anagram_map = defaultdict(list)
7        
8        for s in strs:
9            # Sort the string to create the canonical key
10            # sorted(s) returns a list, so we join it back to a string
11            # or use a tuple as the dict key
12            sorted_key = "".join(sorted(s))
13            
14            # Append original string to the correct group
15            anagram_map[sorted_key].append(s)
16            
17        return list(anagram_map.values())