Group Anagrams in Java DSA: Sorting Key and Count Key, Explained Step by Step

Learn Group Anagrams in Java DSA with two clear approaches — a sort key and a faster count key. Full step-by-step dry runs, beginner-friendly code, and complexity.

1. Introduction

Group Anagrams in Java is a classic hashing problem that feels tricky at first, then clicks once you see the trick. You get a list of words. Some of them are anagrams of each other, which means they use the same letters, just in a different order. Your job is to put the anagrams together in groups.

Take the words eat, tea and ate. They all use the letters a, e and t. So they belong in one group. A word like bat uses different letters, so it goes in its own group.

The task sounds simple, but the catch is how you decide which words are anagrams. You cannot compare every word with every other word. That is slow. Instead, you give each word a signature, and words with the same signature land in the same bucket.

We build the answer in two clear steps. First we make the signature by sorting each word. Then we make a faster signature by counting letters instead of sorting. Both put anagrams in the same group, but one is quicker.

Every approach gets a full, step-by-step dry run on the same seven words. Nothing is skipped, so you can watch each word get a key and drop into its bucket.

2. Understanding the Problem

Let us pin down the rules before writing any code.

• You get an array of strings, for example [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”, “tab”].
• Group the words so that anagrams sit together in the same list.
• Return a list of these groups. The order of the groups does not matter.
• The order of words inside a group does not matter either.

For our seven words the answer has three groups. The words eat, tea and ate form one group. Then tan and nat form another. Finally bat and tab form the last one. Every word lands in exactly one group.

3. Concepts You Need Here

3.1 Anagrams Share One Signature

Two words are anagrams when they hold the same letters the same number of times. So if we can turn each word into a single key that ignores order, all anagrams get the same key.

• Sorting a word gives such a key. The word eat and the word tea both sort to aet.
• Counting letters gives another key. Both eat and tea have one a, one e and one t.

3.2 A HashMap Groups by Key

A HashMap lets us store each key with a list of words that share it. When a new word arrives, we build its key and drop the word into the matching bucket.

• The map key is the signature, like the sorted string aet.
• The map value is a list of words that all share that signature.
• If the key is new, we start a fresh list. If it already exists, we add to it.

4. Approach 1: Sort Each Word as the Key

For each word, sort its letters to build a key. Anagrams always sort to the same string, so they share a key. Use a HashMap from this sorted key to a list of words. Walk the words once, and drop each into its bucket. At the end, the map values are your groups.

4.1 Pseudocode

map = empty map from string to list
 
for word in words:
    key = sort(word)          // sorted letters of the word
    if key not in map:
        map[key] = empty list
    map[key].add(word)        // drop word into its bucket
 
return all values of map

4.2 Pseudocode Explained

Think of it like sorting mail into pigeon holes. Every word gets a label, and words with the same label go into the same hole.

• First we make the label. We sort the letters of the word, so eat becomes aet. Any anagram of eat sorts to aet too, so they all get the same label.
• Next we look for that label in the map. If we have never seen it, we start a new empty list for it. If it is already there, we just reuse it.
• Then we drop the word into that list. So later, when another anagram shows up with the same label, it joins the very same list.
• Once every word is placed, each list in the map is one finished group. We return all those lists as the answer.

4.3 Java Code

import java.util.*;
 
public class GroupAnagramsSort {
 
    public static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> map = new HashMap<>();
        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(word);
        }
        return new ArrayList<>(map.values());
    }
 
    public static void main(String[] args) {
        String[] words = {"eat","tea","tan","ate","nat","bat","tab"};
        System.out.println(groupAnagrams(words));
    }
}

4.4 Java Code Explained

This is the same plan in Java. The one thing to know is that Java cannot sort a String on its own, so we turn it into a char array first.

• Line 6 makes the map. The keys are sorted strings and the values are word lists.
• Lines 8 and 9 turn the word into a char array and sort it, since a String cannot be sorted directly.
• Then line 10 turns the sorted array back into a String, which becomes our key.
• Line 11 uses putIfAbsent to start an empty list when the key is new, so line 12 always has a list to add to.
• Finally line 14 returns all the lists, which are the groups.

4.5 Dry Run of the Sort Key Approach

Let us trace all seven words: eat, tea, tan, ate, nat, bat, tab. For each word we do two things. First we sort its letters into a key. Then we drop the word into the map bucket for that key.

The sorting itself is where beginners lose the thread. So for each word we show the char array changing letter by letter until it is fully sorted. Then a second table shows the map after the word is placed.

Word 0: eat

The char array starts as [e, a, t]. Sorting walks left to right and slides each letter back to its correct spot.

The sorted key is aet. The map is empty, so aet is a new key. A fresh list opens and eat drops in. Map: {aet=[eat]}.

Word 1: tea

The char array starts as [t, e, a]. Both letters after the first need to slide left.

The sorted key is aet again. That key already exists from eat. No new list is needed, so tea joins the bucket. Map: {aet=[eat, tea]}.

Word 2: tan

The char array starts as [t, a, n]. This word has different letters, so watch the key change.

The sorted key is ant. This key is new, so a fresh list opens and tan drops in. Map now has two keys: {aet=[eat, tea], ant=[tan]}.

Word 3: ate

This word starts as the char array [a, t, e]. Its first letter is already smallest, so only the last one moves.

The sorted key is aet, the very first key we made. The aet bucket already holds eat and tea. So ate joins them, and that bucket becomes [eat, tea, ate].

Word 4: nat

The char array starts as [n, a, t]. Only the a needs to move up front.

The sorted key is ant. That key exists from tan, so nat joins it. The ant bucket becomes [tan, nat].

Word 5: bat

The char array starts as [b, a, t]. Just the a jumps ahead of b.

The sorted key is abt, a brand new key. A fresh list opens and bat drops in. The map now holds three keys.

Word 6: tab

The char array starts as [t, a, b]. Both letters after the first slide left.

The sorted key is abt, which bat just created. So tab joins bat, and the last bucket becomes [bat, tab].

Here is the map after each word is placed, so you can see the buckets grow.

After the loop the map holds three keys. The final answer is [[eat, tea, ate], [tan, nat], [bat, tab]].

4.6 What the Dry Run Shows

Look back at the seven sort traces and one pattern jumps out. Words that are anagrams always end at the same sorted array, even though they started in totally different orders.

• The words eat, tea and ate all began differently, yet each one sorted to aet.
• In the same way tan and nat both sorted to ant, so they shared a bucket.
• Finally bat and tab both sorted to abt, landing in the last bucket together.

That is the whole trick. Sorting throws away the original order, so any two anagrams collapse to one identical key. Words with different letters, like bat, can never reach the same sorted string, so they stay apart.

Notice too that the map only ever grows. Each new word either opens a fresh bucket or joins an old one. No word is ever compared with another word directly, which is what makes this fast.

💡 Interview Insight A common question is “why sort the word at all?” Sorting turns every anagram into the same string, so it becomes a perfect group key. Different letters can never sort to the same string.

4.7 Time and Space Cost

• Time is O(n times k log k), where n is the number of words and k is the length of the longest word. Sorting each word costs k log k.
• Space is O(n times k) for the map that holds every word plus its key.

Sorting is clean and easy to remember. Still, that log factor from sorting is extra work. Next we swap sorting for counting and shave it off.

5. Approach 2: Count Letters as the Key

Skip the sorting. For each word, count how many times each of the 26 letters appears. Turn that count into a string like a signature. Anagrams have the same letter counts, so they build the same signature. Use the signature as the map key, just like before. This avoids sorting, so each word is faster to key.

5.1 Pseudocode

map = empty map from string to list
 
for word in words:
    count = array of 26 zeros
    for ch in word:
        count[ch - 'a'] = count[ch - 'a'] + 1
    key = join count values with a separator
    if key not in map:
        map[key] = empty list
    map[key].add(word)
 
return all values of map

5.2 Pseudocode Explained

Same pigeon-hole idea, but we build the label a different way. Instead of sorting, we just count how many of each letter the word has.

• For each word we keep a little scoreboard of 26 numbers, one for every lowercase letter, all starting at zero.
• We walk through the word and tick up the score for each letter we see. The trick ch minus a picks the right slot: a lands on slot 0, b on slot 1, right up to z on slot 25.
• Once the word is done, we glue those 26 scores together into one string. That string is our label. Two anagrams always end with the same scores, so they get the same label.
• From here it is exactly like before. A new label opens a fresh list, and the word drops into its bucket.

5.3 Java Code

import java.util.*;
 
public class GroupAnagramsCount {
 
    public static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> map = new HashMap<>();
        for (String word : words) {
            int[] count = new int[26];
            for (char ch : word.toCharArray()) {
                count[ch - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int c : count) {
                sb.append(c).append('#');
            }
            String key = sb.toString();
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(word);
        }
        return new ArrayList<>(map.values());
    }
 
    public static void main(String[] args) {
        String[] words = {"eat","tea","tan","ate","nat","bat","tab"};
        System.out.println(groupAnagrams(words));
    }
}

5.4 Java Code Explained

The Java code follows the same counting idea. The one new helper is the separator hash, which keeps counts apart so they never blur together.

• Line 8 makes the count array of 26 slots. Java fills a new int array with zeros, so each slot starts clean.
• Lines 9 to 11 walk the word and add one to the right slot. The part ch minus a turns a letter into its slot number.
• Lines 12 to 15 build the key string. We append each count followed by a hash, so 1 and 11 never look the same.
• Line 16 finishes the key. Then line 17 opens a list if needed, and line 18 adds the word.
• Finally line 20 returns all the buckets as the groups.

💡 Why the hash separator? Without a separator, counts a=1, b=1 and a=11 could both read as “11”. The hash between numbers keeps every count clearly apart, so different words never clash by accident.

5.5 Dry Run of the Count Key Approach

Same seven words: eat, tea, tan, ate, nat, bat, tab. For each word we walk its letters and bump one slot per letter. Then the finished count becomes the key.

The count array has 26 slots, one per lowercase letter. Slot a is index 0, slot b is index 1, and so on. To keep tables short, we show only the slots that are not zero after each letter. Every other slot stays at zero the whole time.

Word 0: eat

The count array starts as all zeros. We read eat one letter at a time.

The final count is a=1, e=1, t=1. This key is new, so a fresh list opens and eat drops in. Bucket: [eat].

Word 1: tea

Zeros again. The letters arrive in a different order than eat, but watch the final counts.

The final count is a=1, e=1, t=1, exactly the same as eat. Notice the order the letters came in did not matter. So tea joins eat, and the bucket becomes [eat, tea].

Word 2: tan

Fresh zeros. This word has an n, so its count will differ.

The final count is a=1, n=1, t=1. The n slot makes this key different from eat. So it is new, a fresh bucket opens, and tan drops in. Bucket: [tan].

Word 3: ate

Zeros to start. The letters are a, t, e this time.

The final count is a=1, e=1, t=1, matching eat and tea. So ate joins that bucket, which becomes [eat, tea, ate].

Word 4: nat

Zeros again. The letters n, a, t will match tan.

The final count is a=1, n=1, t=1, the same as tan. So nat joins it, and the bucket becomes [tan, nat].

Word 5: bat

Fresh zeros. Here the b will land in a slot no earlier word touched.

The final count is a=1, b=1, t=1. The b slot makes this a new key. A fresh bucket opens and bat drops in. Bucket: [bat].

Word 6: tab

Zeros to finish the trace. The letters t, a, b will match bat.

The final count is a=1, b=1, t=1, the same as bat. So tab joins bat, and the last bucket becomes [bat, tab].

Here is the summary of all seven words, showing the final counts and the bucket after each one.

The map ends with three keys, giving the same answer: [[eat, tea, ate], [tan, nat], [bat, tab]].

5.6 What the Dry Run Shows

The slot traces make one thing clear. Anagrams reach the same final count no matter what order their letters arrive in.

• For eat the slots filled as e then a then t. For tea they filled as t then e then a. Both still ended at a=1, e=1, t=1.
• That shared final count means eat, tea and ate all built the same key, so they grouped together.
• The word bat hit slot b, which no anagram of eat or tan ever touched, so it stayed in its own bucket.

So counting does the same job as sorting, but it never rearranges anything. It just tallies letters in one quick pass, which is why it runs faster.

💡 Interview Insight If asked “why is counting faster than sorting?”, say that counting a word is a single pass over its letters, which is O(k). Sorting costs O(k log k). Over many words that log factor adds up, so counting wins.

5.7 Time and Space Cost

• Time is O(n times k), where n is the number of words and k is the longest word length. Counting each word is a single pass with no sorting.
• Space is O(n times k) for the map and its word lists, plus a fixed 26-slot array we reuse per word.

This is faster than sorting because we drop the log factor. For lowercase words, the count key is the version interviewers like to see.

6. Comparing the Two Approaches

Both approaches return the same groups. They only differ in how they build the key for each word.

Both use the same amount of space, since both store every word in the map. What separates them is the key-building cost. Sorting pays a log factor per word, while counting does not.

In an interview, mention the sort key first to show the idea clearly. Then move to the count key for speed. That progression tells a clean story and shows you can optimise.

💡 Interview Insight If asked what happens with uppercase or unicode letters, be honest. The count key of size 26 assumes lowercase a to z. For wider input, either grow the array or fall back to the sort key, which works for any characters.

7. Common Mistakes and Edge Cases

A few small traps catch beginners on Group Anagrams. Keep them in mind.

• Comparing every word with every other word is slow and needless. The key trick avoids that O(n squared) work.
• Forgetting the separator in the count key can merge two counts into one number and cause wrong groups.
• Using the 26-slot count on uppercase or unicode input breaks the ch minus a math.
• A single word with no anagrams still forms a group of one, which is correct.
• An empty input array should return an empty list, so handle that cleanly.

Run a single-word case and an empty-array case through your code before calling it done. These quiet cases catch more bugs than the obvious ones.

8. Conclusion

Group Anagrams in Java teaches a habit you will reuse everywhere. When you must group items that look different but mean the same, give each one a signature and let a map do the grouping.

Our seven-word traces showed the payoff clearly. Sorting each word built a shared key, so anagrams met in one bucket. Counting letters built the same shared key without sorting, which runs faster.

So take the pattern, not just the answer. Turn each item into a canonical key, then group by that key in a map. Reach for the count key when the alphabet is small, and keep the sort key handy for anything wider.

That signature habit turns many string and array problems from tricky into routine. It will serve you well on the harder grouping problems waiting further down the list.

9. Interview Questions

10. Further Reading

• LeetCode Group Anagrams problem — practice the original problem and submit your own solution.
• Oracle Java HashMap documentation — the official reference for the map used to group the words.
• Previous in this series: Valid Anagram in Java — check whether two words use the exact same letters using a count array.
• Next in this series: Top K Frequent Elements in Java — find the most common numbers using a frequency map and a heap or bucket sort.