Given a sequence of words, print all anagrams together

Problem Statement

Given an array of words, group all anagrams together. Two words are anagrams if they contain the same characters with the same frequencies.

Example:

• Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
• Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Approach 1: Brute Force (Compare Each Pair)

Intuition

Compare each word with every other word to check if they are anagrams. Group them accordingly.

Algorithm

1. For each word, compare with all other words
2. Two words are anagrams if their sorted versions are equal
3. Mark processed words to avoid duplicates
4. Group anagrams together

import java.util.*;

public class Solution {
    private boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        return Arrays.equals(arr1, arr2);
    }
    
    public List<List<String>> groupAnagrams(String[] strs) {
        int n = strs.length;
        boolean[] used = new boolean[n];
        List<List<String>> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            
            List<String> group = new ArrayList<>();
            group.add(strs[i]);
            used[i] = true;
            
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && areAnagrams(strs[i], strs[j])) {
                    group.add(strs[j]);
                    used[j] = true;
                }
            }
            
            result.add(group);
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n² * m log m) - Comparing n² pairs, each comparison takes O(m log m) for sorting
• Space Complexity: O(n * m) - Storing all strings

Approach 2: Sort and Use HashMap (Optimal)

Intuition

All anagrams will have the same sorted string. Use the sorted string as a key in a HashMap to group anagrams.

Algorithm

1. For each word, sort its characters to get a key
2. Use this key in a HashMap
3. All words with the same key are anagrams
4. Return all groups

import java.util.*;

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(groups.values());
    }
}

Complexity Analysis

• Time Complexity: O(n * m log m) - Sorting each of n strings of length m
• Space Complexity: O(n * m) - Storing all strings in HashMap

Approach 3: Character Count as Key (Even Better)

Intuition

Instead of sorting, use character frequency count as the key. This avoids the O(m log m) sorting cost.

Algorithm

1. For each word, count frequency of each character
2. Convert this count to a string key (e.g., "a2b1c3")
3. Group by this key

import java.util.*;

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String s : strs) {
            // Count character frequencies
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            // Create key from count
            StringBuilder key = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                key.append('#');
                key.append(count[i]);
            }
            
            String keyStr = key.toString();
            groups.computeIfAbsent(keyStr, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(groups.values());
    }
}

Complexity Analysis

• Time Complexity: O(n * m) - Counting each of n strings of length m
• Space Complexity: O(n * m)

Approach 4: Prime Number Product

Intuition

Assign a unique prime number to each character. The product of primes for a word will be unique for each anagram group.

Note: This approach can have overflow issues for long strings. Use with caution or combine with modular arithmetic.

Complexity Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Printing Anagrams Together

To print anagrams in sorted order within groups:

Key Takeaways

1. Sorted string as key is the most intuitive approach
2. Character count as key avoids sorting cost, giving O(nm) instead of O(nm log m)
3. Prime product is clever but has overflow issues
4. All anagrams share the same "signature" - sorted form or character count
5. This is LeetCode 49 and a very common interview question
6. Related problems: Valid Anagram, Find All Anagrams in a String