In string manipulation, determining whether two words contain the exact same characters in different orders is a classic challenge. Two such words are called anagrams (e.g., silent and listen). A common backend engineering task is grouping a massive list of words into buckets of anagrams.

Given an array of strings, our goal is to group the anagrams together. For example, given the input array ["eat", "tea", "tan", "ate", "nat", "bat"], we want to identify and group the matching sets to output [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]].

To accomplish this efficiently for large dictionaries containing thousands of words, we need to map strings to a common canonical form. This guide details how to solve this using a hashing strategy in Java.

Real-World Analogy: The Alphabetical Folder Filing System

To visualize the sorting-and-grouping strategy, imagine a clerk organizing a stack of unsorted word cards.

To file them systematically, the clerk decides on a standardized indexing rule:

  1. When the clerk picks up a card (e.g., tea), they rearrange its letters alphabetically to create a unique fingerprint (e.g., aet).
  2. The clerk checks their filing cabinet for a folder labeled with this fingerprint (aet).
  3. If no such folder exists, they create one.
  4. They file the original card (tea) inside the aet folder.
  5. As they repeat this process, cards like eat and ate also sort to aet and end up in the same folder.
At the end of the day, each folder in the cabinet contains a group of perfect anagrams.

Algorithmic Solutions

1. The Brute-Force Approach (O(N² * K) Time)

We can check every pair of strings using a nested loop, checking if they are anagrams. When we find matches, we group them and mark them as visited. This quadratic approach is highly inefficient for large inputs, especially when dealing with thousands of words.

2. HashMap Categorization (O(N * K log K) Time)

We use a HashMap where the key is the sorted canonical representation of a word, and the value is a list of all strings that match that key:

  • We loop through the input strings.
  • For each word, we convert it to a character array, sort it alphabetically, and construct a new string to serve as our unique map key.
  • We check if the key is present in the map, initialize the list if absent, and append our original word to it.
  • Finally, we return the values of the map as our grouped list.
This runs in linear-logarithmic time, making it highly suitable for large dictionaries.

Step-by-Step Scenario Walkthrough

Let's trace the HashMap strategy on the array ["eat", "tea", "tan"]:

  • Word "eat": Alphabetical sort gives key "aet". Key "aet" is missing. We create a list and insert the word. Map: {"aet": ["eat"]}.
  • Word "tea": Sort gives key "aet". The key already exists. We append tea to the list. Map: {"aet": ["eat", "tea"]}.
  • Word "tan": Sort gives key "ant". Key is missing. We create a list and insert the word. Map: {"aet": ["eat", "tea"], "ant": ["tan"]}.
The loop finishes, and the map values are returned as a grouped list.

Key Code Explanations

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

  • char[] chars = str.toCharArray(); Arrays.sort(chars);: Standardizes any anagram permutation into a single unique sorted key representation.
  • map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);: 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)
    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 & Complexity Analysis

Our optimized HashMap solution runs in O(N * K log K) time complexity (where N is the number of strings and K is the maximum string length, due to sorting character arrays of size K) and uses O(N * K) space to store the map. By mapping varying anagrams to a standardized canonical key, we group related strings in a single pass.