Group Anagrams — Case Normalization Bug in Production

Anagram grouping shows up more often in the real world than you'd think. Search engines use it to match synonyms and spelling variants. DNA analysis tools cluster gene sequences that are permutations of one another. Even autocorrect relies on letter-frequency fingerprints to suggest words. If you've ever searched 'best pasta recipe' and also gotten results for 'best tapas recipe', you've brushed up against anagram-aware text processing in the wild.

The naive approach — comparing every word against every other word — works, but it scales like a nightmare. With just 10,000 words you're looking at 100 million comparisons. The real problem is that we keep re-doing work we've already done. Hashing solves this by collapsing the expensive comparison into a single, cheap key lookup. Once you reduce 'LISTEN' and 'SILENT' to the same key, grouping them is O(1) — it's just putting a book on the right shelf.

By the end of this article you'll understand two distinct hashing strategies for this problem (sorted key vs. frequency array key), know exactly when to reach for each one, be able to implement both from scratch, and walk into an interview ready to discuss trade-offs, edge cases, and optimisations with confidence.

Building the Mental Model — What Makes a Good Anagram Key?

Before writing a single line of code, let's nail down the insight that makes this problem tractable.

Two words are anagrams if and only if they contain exactly the same characters with exactly the same frequencies. 'RACE' and 'CARE' both have one R, one A, one C, one E. That's it — that's the entire definition.

So a perfect key is any representation that captures character frequencies and nothing else. Order shouldn't matter. Two properties must hold: (1) anagrams must produce the identical key, and (2) non-anagrams must produce different keys. If your key satisfies both, you can use a HashMap to bucket words by key in a single linear pass.

There are two popular ways to build this key:

• Sort the letters alphabetically. 'RACE' → 'ACER'. 'CARE' → 'ACER'. Same key, same bucket.
• Build a 26-element frequency array, then serialise it into a string like '1#0#1#1#1#0#...' (one count per letter a–z).

Both are valid. Sorting costs O(k log k) per word where k is the word length. The frequency array costs O(k) per word. For short words the difference is negligible; for very long strings the frequency array wins. Understanding this trade-off is exactly what separates a good interview answer from a great one.

import java.util.Arrays;

public class AnagramKeyDemo {

    public static String sortedKey(String word) {
        char[] characters = word.toLowerCase().toCharArray();
        Arrays.sort(characters);
        return new String(characters);
    }

    public static String frequencyKey(String word) {
        int[] letterCounts = new int[26];
        for (char ch : word.toLowerCase().toCharArray()) {
            letterCounts[ch - 'a']++;
        }
        StringBuilder keyBuilder = new StringBuilder();
        for (int count : letterCounts) {
            keyBuilder.append(count).append('#');
        }
        return keyBuilder.toString();
    }

    public static void main(String[] args) {
        String[] testWords = {"listen", "silent", "enlist", "race", "care", "hello"};
        System.out.println("Word       | Sorted Key  | Frequency Key (truncated)");
        System.out.println("-----------|-------------|---------------------------");
        for (String word : testWords) {
            String sorted = sortedKey(word);
            String freq   = frequencyKey(word).substring(0, 20) + "...";
            System.out.printf("%-10s | %-11s | %s%n", word, sorted, freq);
        }
    }
}

The Full Solution — Grouping Words With a HashMap in One Pass

Now that we have a reliable key function, the grouping algorithm itself is almost embarrassingly simple. One HashMap, one loop, done.

The map's keys are our anagram fingerprints. The map's values are lists of words that share that fingerprint. We iterate through every word once, compute its key, and append the word to the correct list. At the end, we return all the lists.

Total time complexity: O(n · k log k) using sorted keys, or O(n · k) using frequency keys, where n is the number of words and k is the average word length. Space complexity: O(n · k) to store all words in the map.

Notice we never compare two words against each other. We never nest loops. That's the power of hashing: it transforms a pairwise comparison problem into a single-pass bucketing problem.

One practical thing worth noting — Java's getOrDefault on a HashMap is your friend here. It lets you avoid an explicit null-check before adding to the list, which keeps the core logic clean and readable. Production code is read far more often than it's written, so clarity matters.

import java.util.*;

public class GroupAnagrams {

    public static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> anagramBuckets = new HashMap<>();
        for (String word : words) {
            String canonicalKey = buildSortedKey(word);
            anagramBuckets
                .computeIfAbsent(canonicalKey, k -> new ArrayList<>())
                .add(word);
        }
        return new ArrayList<>(anagramBuckets.values());
    }

    private static String buildSortedKey(String word) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    public static List<List<String>> groupAnagramsFast(String[] words) {
        Map<String, List<String>> anagramBuckets = new HashMap<>();
        for (String word : words) {
            String canonicalKey = buildFrequencyKey(word);
            anagramBuckets
                .computeIfAbsent(canonicalKey, k -> new ArrayList<>())
                .add(word);
        }
        return new ArrayList<>(anagramBuckets.values());
    }

    private static String buildFrequencyKey(String word) {
        int[] charFrequencies = new int[26];
        for (char ch : word.toCharArray()) {
            charFrequencies[ch - 'a']++;
        }
        StringBuilder key = new StringBuilder();
        for (int frequency : charFrequencies) {
            key.append(frequency).append('#');
        }
        return key.toString();
    }

    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println("Input words: " + Arrays.toString(words));
        System.out.println();
        List<List<String>> groupedBySortedKey = groupAnagrams(words);
        System.out.println("Grouped (sorted-key approach):");
        for (List<String> group : groupedBySortedKey) {
            System.out.println("  " + group);
        }
        System.out.println();
        List<List<String>> groupedByFrequency = groupAnagramsFast(words);
        System.out.println("Grouped (frequency-key approach):");
        for (List<String> group : groupedByFrequency) {
            System.out.println("  " + group);
        }
        String[] singleWord = {"hello"};
        List<List<String>> singleResult = groupAnagrams(singleWord);
        System.out.println();
        System.out.println("Single word input: " + singleResult);
        String[] allAnagrams = {"abc", "bca", "cab", "bac"};
        List<List<String>> allSameGroup = groupAnagrams(allAnagrams);
        System.out.println("All anagrams input: " + allSameGroup);
    }
}

Real-World Patterns — When Grouping Anagrams Actually Comes Up

This problem isn't just a coding exercise — the underlying pattern (hash by canonical form, group by hash) appears constantly in production software.

Search query normalisation: search engines often cluster queries that are anagram variants or phonetic equivalents so that a single indexed result can serve multiple query forms. The sorted-key trick is a lightweight first-pass filter before heavier NLP kicks in.

Duplicate detection in data pipelines: imagine you're ingesting CSV files from multiple sources. Column headers might arrive in different orders — 'name, age, city' vs 'age, city, name'. Sorting the headers and hashing them is a fast way to detect that two files share the same schema before attempting a merge.

Bioinformatics: DNA subsequences that are permutations of each other sometimes bind to the same protein receptor. Grouping them by character frequency is a preprocessing step in similarity analysis.

The deeper lesson: any time you need to group items that are 'equivalent under reordering', the canonical-key-plus-HashMap pattern is your go-to. You're not solving 'group anagrams' — you're solving 'equivalence class partitioning', which is one of the most reusable ideas in computer science.

import java.util.*;

public class SchemaGrouper {

    public static Map<String, List<String>> groupEquivalentSchemas(String[] schemas) {
        Map<String, List<String>> equivalenceGroups = new HashMap<>();
        for (String schema : schemas) {
            String[] columns = schema.split(",");
            Arrays.sort(columns);
            String canonicalSchema = String.join(",", columns);
            equivalenceGroups
                .computeIfAbsent(canonicalSchema, k -> new ArrayList<>())
                .add(schema);
        }
        return equivalenceGroups;
    }

    public static void main(String[] args) {
        String[] incomingSchemas = {
            "name,age,city",
            "age,city,name",
            "city,name,age",
            "id,email,phone",
            "phone,id,email",
            "name,salary"
        };
        Map<String, List<String>> groups = groupEquivalentSchemas(incomingSchemas);
        System.out.println("Equivalent schema groups:");
        System.out.println("=========================");
        int groupNumber = 1;
        for (Map.Entry<String, List<String>> entry : groups.entrySet()) {
            System.out.println("Group " + groupNumber + " (canonical: " + entry.getKey() + ")");
            for (String schema : entry.getValue()) {
                System.out.println("   -> " + schema);
            }
            groupNumber++;
        }
    }
}

Edge Cases and Performance Gotchas

Even with a correct key function, there are edge cases that can trip you up in production or in an interview.

Empty input: an empty string produces an empty key. For sorted-key, an empty char array sorts to empty string. For frequency key, all counts are zero. Both work, but the resulting key is a valid empty string. Your code should handle this without special-casing.

Single-character words: Both keys work fine. For sorted-key, the character remains itself. For frequency key, only one count is non-zero.

Unicode and non-ASCII characters: The frequency-array approach with int[26] only works for lowercase English letters. For Unicode, you'd need a larger array (e.g., int[65536] for full Unicode plane) or a different strategy like counting character code points. The sorted-key approach handles any characters that implement Comparable.

Very large input (millions of words): Memory becomes a concern. The HashMap stores every word reference — space is O(n·k). You can reduce memory by not storing the words themselves but storing indices, or by using a streaming approach if grouping isn't needed all at once.

Punctuation and spaces: The problem usually assumes only letters. If punctuation is present, you must decide whether to include or strip it. Typically you'd filter to letters only first.

import java.util.*;

public class EdgeCasesDemo {

    // Key function that filters non-letters and lowercases
    public static String robustSortedKey(String word) {
        StringBuilder lettersOnly = new StringBuilder();
        for (char ch : word.toLowerCase().toCharArray()) {
            if (ch >= 'a' && ch <= 'z') {
                lettersOnly.append(ch);
            }
        }
        char[] chars = lettersOnly.toString().toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    public static void main(String[] args) {
        String[] tricky = {"", "a", "listen!", "SILENT?"};
        for (String w : tricky) {
            System.out.println("Word: '" + w + "' -> key: '" + robustSortedKey(w) + "'");
        }
    }
}

Interview Strategy: Picking the Right Approach

When you see 'group anagrams' in an interview, your instinct should be: canonical key + HashMap. But the interviewer will probe your understanding of trade-offs.

Sorted key is the safest first answer. It's simple to implement, easy to explain, and works for 99% of cases. Start here.

Frequency key is the optimisation follow-up. If the interviewer asks 'can you do better?', say: 'I can avoid sorting by using a fixed-size array for counting, which reduces per-word cost from O(k log k) to O(k).' Then implement it.

Space optimisation might come up: 'Can you reduce memory?' You can use a Trie to store words by their sorted path, or use integer encoding (e.g., prime product) but that's risky due to overflow.

Edge cases to discuss: empty string, single character, all same word, all anagrams, Unicode.

Generalisation: Be prepared to show you've understood the underlying equivalence-class pattern. The interviewer may ask how you'd adapt this to group columns, genes, or phone numbers.

Performance numbers: For n=10^5 and k=10, sorted key takes ~10^5 10 log 10 ≈ 3.3 million operations. Frequency key takes 10^5 10 = 1 million. The difference is measurable but often irrelevant in practice. Mention that context matters.

// Key points to mention in an interview:
// 1. Complexity: O(n·k log k) with sorted, O(n·k) with frequency.
// 2. Space: O(n·k) for the map.
// 3. Edge cases: empty, case, punctuation, Unicode, large input.
// 4. Generalisation: canonical-form + HashMap is a pattern.
// 5. If memory is constrained, consider using indices instead of strings.

// Example: group anagrams returning indices
public Map<String, List<Integer>> groupAnagramIndices(String[] words) {
    Map<String, List<Integer>> groups = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
        String key = buildSortedKey(words[i]);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(i);
    }
    return groups;
}

Frequently Asked Questions