Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]

Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

Explanation:

• There is no string in strs that can be rearranged to form "bat".
• The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
• The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [""]

Output: [[""]]

Example 3:

Input: strs = [“a”]

Output: [[“a”]]

Constraints:

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

Approach: Sort Each String as Key (Optimal Solution)

Algorithm

1. Create a hash map that maps a sorted string key to a list of its anagrams
2. Iterate through each string in the array
3. Convert the string to a character array, sort it, and rebuild the sorted key
4. If the key already exists, append the string to the list; otherwise, create a new list
5. Return all the grouped lists as the final answer

Time & Space Complexity

• Time Complexity: O(n · k log k) - where n is the number of strings and k is the maximum length of a string; sorting each string dominates the cost
• Space Complexity: O(n · k) - the hash map stores every string

Java Implementation

import java.util.*;

public class GroupAnagrams {

    /**
     * Group anagrams together.
     * @param strs Array of strings
     * @return List of groups, each containing strings that are anagrams
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        // Map from sorted key -> list of original strings
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);

            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(map.values());
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        String[] strs1 = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result1 = groupAnagrams(strs1);
        System.out.println("Input: strs = [\"eat\", \"tea\", \"tan\", \"ate\", \"nat\", \"bat\"]");
        System.out.println("Output: " + result1); // Expected: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

        // Test case 2
        String[] strs2 = {""};
        List<List<String>> result2 = groupAnagrams(strs2);
        System.out.println("Input: strs = [\"\"]");
        System.out.println("Output: " + result2); // Expected: [[""]]

        // Test case 3
        String[] strs3 = {"a"};
        List<List<String>> result3 = groupAnagrams(strs3);
        System.out.println("Input: strs = [\"a\"]");
        System.out.println("Output: " + result3); // Expected: [["a"]]
    }
}

Alternative Implementation with Count Array Key

Since all strings consist of lowercase English letters, an alternative is to build a unique key from a character count array. This avoids the O(k log k) sorting cost and is O(k) per string.

import java.util.*;

public class GroupAnagramsCountKey {

    /**
     * Group anagrams together using a character-count key.
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }

            // Build key like "#1#2#0#..."
            StringBuilder sb = new StringBuilder();
            for (int n : count) {
                sb.append('#').append(n);
            }
            String key = sb.toString();

            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

Example Walkthrough

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

1. “eat”: sorted key = “aet”. Map: {“aet” -> [“eat”]}
2. “tea”: sorted key = “aet”. Already exists. Map: {“aet” -> [“eat”, “tea”]}
3. “tan”: sorted key = “ant”. Map: {“aet” -> [“eat”, “tea”], “ant” -> [“tan”]}
4. “ate”: sorted key = “aet”. Map: {“aet” -> [“eat”, “tea”, “ate”], “ant” -> [“tan”]}
5. “nat”: sorted key = “ant”. Map: {“aet” -> [“eat”, “tea”, “ate”], “ant” -> [“tan”, “nat”]}
6. “bat”: sorted key = “abt”. Map adds “abt” -> [“bat”]

Final result: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Key Points

1. Canonical Key: Two strings are anagrams if and only if they sort to the same string
2. HashMap Grouping: Use the canonical key as the hash map key to group efficiently
3. Any Order: The problem allows returning groups in any order
4. Edge Cases: Correctly handles empty strings and single-character strings
5. Complexity Trade-off: Sorting-based solution is O(n · k log k); count-array approach is O(n · k)