Understanding Group Anagrams in Java

Introduction & Problem Explanation

The Group Anagrams problem asks us to group an array of strings such that all strings that are anagrams of each other are placed in the same sublist.

For example, given the input array ["eat", "tea", "tan", "ate", "nat", "bat"], we want to return a list of groups: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]. The groups can be returned in any order. The challenge is organizing these strings efficiently when the array contains thousands of words.

The Algorithmic Approach

1. The Naive Approach (O(n² * k))

We can check every pair of strings using a nested loop, comparing if they are anagrams. When we find matches, we group them. This has a quadratic complexity of O(n² * k) where k is the maximum length of a string, which is extremely slow for larger datasets.

2. HashMap with Sorted Key Fingerprints (O(n * k log k))

We can use a HashMap where the key is the sorted version of a string (its canonical form/fingerprint), and the value is a list of all strings that match that sorted key.

• We iterate through each string in the array.
• For each string, we convert it to a character array, sort it alphabetically, and convert it back to a string to form our key.
• We check if the key is already in the map. If not, we add it with a new list. Then, we add the original string to that key's list.

This runs in O(n * k log k) time (where n is the number of strings and k is the maximum string length), which is highly efficient.

Step-by-Step Execution Walkthrough

Let's trace the HashMap-based grouping on the array strs = ["eat", "tea", "tan", "ate", "nat", "bat"]:

1. Step 1 (Initialization): Initialize an empty HashMap: map = {}.
2. Step 2 (Word "eat"):
   • Sort the letters: "eat" sorted alphabetically becomes "aet".
   • Check if key "aet" exists in the map. It does not.
   • Create a new list for "aet" and add "eat". Map: {"aet": ["eat"]}.
3. Step 3 (Word "tea"):
   • Sort the letters: "tea" sorted becomes "aet".
   • Key "aet" already exists in the map.
   • Add "tea" to its list. Map: {"aet": ["eat", "tea"]}.
4. Step 4 (Word "tan"):
   • Sort the letters: "tan" sorted becomes "ant".
   • Key "ant" does not exist. Create list and add. Map: {"aet": ["eat", "tea"], "ant": ["tan"]}.
5. Step 5 (Word "ate"):
   • Sort the letters: "ate" sorted becomes "aet".
   • Add to list: Map: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}.
6. Step 6 (Word "nat"):
   • Sort the letters: "nat" sorted becomes "ant".
   • Add to list: Map: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}.
7. Step 7 (Word "bat"):
   • Sort the letters: "bat" sorted becomes "abt". Key does not exist.
   • Add: Map: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}.
8. Step 8 (Completion): The iteration is complete. We return the values of the map as a list of lists: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• char[] chars = s.toCharArray(); Arrays.sort(chars);: Standardizes any anagram permutation into a single unique sorted key representation.
• map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);: An elegant Java utility that initializes a new list for a key if it is missing, then adds the string, avoiding nested null checks.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.*;

public class GroupAnagrams {

    // Brute Force - O(n^2 * k log k)
    public List<List<String>> groupAnagramsBrute(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        boolean[] visited = new boolean[strs.length];
        for (int i = 0; i < strs.length; i++) {
            if (visited[i]) continue;
            List<String> group = new ArrayList<>();
            group.add(strs[i]);
            visited[i] = true;
            for (int j = i + 1; j < strs.length; j++) {
                if (!visited[j] && isAnagram(strs[i], strs[j])) {
                    group.add(strs[j]);
                    visited[j] = true;
                }
            }
            res.add(group);
        }
        return res;
    }

    private boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int c : count) if (c != 0) return false;
        return true;
    }

    // Optimized - O(n * k log k) with HashMap
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        GroupAnagrams solver = new GroupAnagrams();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

        System.out.println("--- Group Anagrams Demonstration ---");
        System.out.println("Input: " + Arrays.toString(strs));

        List<List<String>> result = solver.groupAnagrams(strs);
        System.out.println("Grouped Anagrams: " + result);
    }
}

Conclusion

Solving the Group Anagrams problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.