In this tutorial, I will demonstrate how to group anagrams from a List of strings in Java. This is a popular coding interview problem that helps you understand HashMap, string manipulation, sorting, and character frequency counting.
Two strings are anagrams if they contain the same characters with the same frequencies, but the characters may appear in a different order. For example, "eat", "tea", and "ate" are anagrams because each string contains the letters 'a', 'e', and 't' exactly once.
The goal is to take a collection of strings and place all anagrams into the same group. Strings that do not have any matching anagrams should appear in their own groups.
In this tutorial, you will learn two approaches to grouping anagrams in Java. The first uses sorting and HashMap, while the second uses character frequency counting. I will also explain each approach step by step, provide a dry run, compare time complexity, and discuss important edge cases.
1. Problem Statement
Write a Java program to group anagrams from a List of strings.
Each group should contain strings that are anagrams of one another.
Example 1
Input: ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [ [eat, tea, ate], [tan, nat], [bat] ]
Explanation:
"eat","tea", and"ate"belong to the same group."tan"and"nat"belong to another group."bat"has no matching anagram, so it forms its own group.
Example 2
Input: ["abc", "bca", "cab", "dog", "god", "cat"] Output: [ [abc, bca, cab], [dog, god], [cat] ]
The order of groups does not affect whether the grouping is logically correct. However, the implementations in this tutorial use LinkedHashMap to produce predictable group order based on the first appearance of each group.
2. What Is an Anagram?
An anagram is formed by rearranging the characters of another string without adding or removing characters.
For two strings to be anagrams, they must contain the same characters with identical frequencies.
Consider these examples:
| First String | Second String | Anagrams? | Explanation |
|---|---|---|---|
| listen | silent | Yes | Same characters and frequencies |
| eat | tea | Yes | Same letters in different order |
| hello | world | No | Different characters |
| aab | abb | No | Character frequencies differ |
Understanding this property is the key to solving the group anagrams problem.
3. Method 1: Group Anagrams Using Sorting and HashMap
The most common approach is to sort the characters of each string and use the sorted result as a key in a Map.
Anagram strings contain the same characters, so sorting their characters produces the same result.
For example:
Original String Sorted Characters eat aet tea aet ate aet tan ant nat ant bat abt
Notice that all anagrams produce identical sorted keys.
The program can therefore use each sorted key to identify the correct group.
How the Algorithm Works
- Create a Map where the key is a sorted string and the value is a List of matching anagrams.
- Iterate through each string in the input list.
- Convert the string into a character array.
- Sort the character array using
Arrays.sort(). - Convert the sorted characters into a String to create a grouping key.
- Add the original string to the List associated with that key.
- Return all the grouped Lists.
Java Program Using HashMap and Sorting
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class GroupAnagrams {
/**
* Groups anagram strings together.
*
* @param words input list of strings
* @return list containing groups of anagrams
*/
public static List<List<String>> groupAnagrams(
List<String> words) {
Map<String, List<String>> anagramMap =
new LinkedHashMap<>();
for (String word : words) {
// Convert string to character array
char[] characters = word.toCharArray();
// Sort characters to create a common key
Arrays.sort(characters);
String key = new String(characters);
// Add the original word to its group
anagramMap.computeIfAbsent(
key, k -> new ArrayList<>()
).add(word);
}
return new ArrayList<>(anagramMap.values());
}
public static void main(String[] args) {
List<String> words = Arrays.asList(
"eat", "tea", "tan", "ate", "nat", "bat"
);
List<List<String>> result =
groupAnagrams(words);
System.out.println("Original List: " + words);
System.out.println("Grouped Anagrams:");
for (List<String> group : result) {
System.out.println(group);
}
}
}Output
Original List: [eat, tea, tan, ate, nat, bat] Grouped Anagrams: [eat, tea, ate] [tan, nat] [bat]
Note: The program uses LinkedHashMap, which extends HashMap and preserves the insertion order of groups. If you use a regular HashMap, the group order is not guaranteed.
4. Step-by-Step Explanation
Step 1: Create a Map for Anagram Groups
Map<String, List<String>> anagramMap =
new LinkedHashMap<>();The Map stores sorted character sequences as keys and their corresponding anagram groups as values.
For example, the key "aet" identifies all strings containing exactly the letters 'a', 'e', and 't'.
Step 2: Iterate Through Each String
for (String word : words) {The enhanced for loop processes each word from the input list.
Step 3: Convert the String into a Character Array
char[] characters = word.toCharArray();The toCharArray() method converts the string into a character array.
For example, "tea" becomes:
[t, e, a]
Step 4: Sort the Characters
Arrays.sort(characters);The Arrays.sort() method sorts the characters in ascending order.
After sorting:
[a, e, t]
The strings "eat", "tea", and "ate" all produce this same sorted character array.
Step 5: Create the Grouping Key
String key = new String(characters);This converts the sorted character array into a String.
For all three anagrams "eat", "tea", and "ate", the generated key is "aet".
Step 6: Add the Word to the Correct Group
anagramMap.computeIfAbsent(
key, k -> new ArrayList<>()
).add(word);The computeIfAbsent() method checks whether the key already has a corresponding List.
- If the key is absent, it creates a new ArrayList.
- If the key exists, it retrieves the existing ArrayList.
- The original word is added to that List.
For example, after processing the strings "eat", "tea", and "ate", the map contains the following logical entry:
aet = [eat, tea, ate]
Step 7: Return the Anagram Groups
return new ArrayList<>(anagramMap.values());The values() method returns the Lists stored in the Map.
Creating a new ArrayList produces the required List<List<String>> result.
5. Dry Run: Grouping Anagrams
Consider this input:
["eat", "tea", "tan", "ate", "nat", "bat"]
The program processes each word, sorts its characters, and adds it to the matching group.
| Step | Word | Sorted Key | Updated Group |
|---|---|---|---|
| 1 | eat | aet | [eat] |
| 2 | tea | aet | [eat, tea] |
| 3 | tan | ant | [tan] |
| 4 | ate | aet | [eat, tea, ate] |
| 5 | nat | ant | [tan, nat] |
| 6 | bat | abt | [bat] |
After all strings have been processed, the Map logically contains:
aet = [eat, tea, ate] ant = [tan, nat] abt = [bat]
The final result is:
[ [eat, tea, ate], [tan, nat], [bat] ]
6. Method 2: Group Anagrams Using Character Frequency
Another approach is to count the frequency of every character in each string.
Two strings are anagrams if they contain the same characters with identical frequencies.
For example:
String: eat a = 1 e = 1 t = 1 String: tea a = 1 e = 1 t = 1
Because the frequency information is identical, both strings belong to the same group.
For this approach, assume that each input string contains only lowercase English letters from 'a' to 'z'.
You can represent the character frequencies using an integer array of length 26.
Java Program Using Character Frequency
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class GroupAnagramsUsingFrequency {
public static List<List<String>> groupAnagrams(
List<String> words) {
Map<String, List<String>> anagramMap =
new LinkedHashMap<>();
for (String word : words) {
int[] frequency = new int[26];
// Count frequency of each character
for (char ch : word.toCharArray()) {
frequency[ch - 'a']++;
}
// Build a unique key from character counts
StringBuilder keyBuilder = new StringBuilder();
for (int count : frequency) {
keyBuilder.append('#').append(count);
}
String key = keyBuilder.toString();
// Group strings with the same frequency key
anagramMap.computeIfAbsent(
key, k -> new ArrayList<>()
).add(word);
}
return new ArrayList<>(anagramMap.values());
}
public static void main(String[] args) {
List<String> words = Arrays.asList(
"eat", "tea", "tan", "ate", "nat", "bat"
);
List<List<String>> result =
groupAnagrams(words);
System.out.println("Grouped Anagrams:");
for (List<String> group : result) {
System.out.println(group);
}
}
}Output
Grouped Anagrams: [eat, tea, ate] [tan, nat] [bat]
How the Frequency-Based Approach Works
For every input string, the algorithm creates a frequency array:
int[] frequency = new int[26];Each position represents one lowercase English letter.
For example:
- Index 0 represents 'a'.
- Index 1 represents 'b'.
- Index 2 represents 'c'.
- Index 25 represents 'z'.
The statement:
frequency[ch - 'a']++;increments the count associated with the current character.
Next, the program converts the frequency array into a string key.
The separator character # is important because it prevents ambiguity between adjacent frequency values.
For example, the sequences of counts [1, 11] and [11, 1] should not generate the same key.
Using separators produces distinct representations such as #1#11 and #11#1.
Strings with identical frequency keys are then placed in the same group.
Important Limitation
This frequency-based implementation supports lowercase English letters only.
It does not directly support uppercase letters, spaces, punctuation, or arbitrary Unicode characters.
For those inputs, use the sorting-based approach or redesign the frequency representation.
7. Time and Space Complexity
Let's compare the sorting-based and character-frequency approaches.
Assume:
nis the number of strings.kis the maximum length of a string.uis the number of unique anagram groups.
| Approach | Expected Time | Additional Space | Best Use Case |
|---|---|---|---|
| Sorting + HashMap | O(n × k log k) | O(n × k) | General-purpose solution |
| Frequency + HashMap | O(n × (k + 26)) | O(n + u × 26) | Lowercase English letters |
These bounds assume efficient average-case hash-map operations and refer to additional storage, including grouping keys and result lists.
Sorting-Based Approach
Sorting a string containing k characters requires O(k log k) time in the general case.
Since there are n strings, the total expected time complexity is:
O(n × k log k)
The map stores the original string references in groups and maintains sorted-character keys, resulting in O(n × k) additional space in the worst case.
Frequency-Based Approach
The frequency approach scans each string and counts its characters.
For lowercase English letters, it also builds a fixed-size key containing 26 counts.
Its expected time complexity is:
O(n × (k + 26))
Because 26 is constant, this is commonly simplified to O(n × k) for nonempty strings.
The frequency approach avoids sorting and can be more efficient for long strings containing only lowercase English letters.
8. Handling Important Edge Cases
Case 1: Empty Input List
Input: [] Output: []
The program returns an empty List because there are no strings to group.
Case 2: Single String
Input: ["java"] Output: [[java]]
A string without matching anagrams forms its own group.
Case 3: All Strings Are Anagrams
Input: ["abc", "bca", "cab"] Output: [[abc, bca, cab]]
All strings belong to one group because their characters have the same frequencies.
Case 4: No Strings Are Anagrams
Input: ["cat", "dog", "fish"] Output: [[cat], [dog], [fish]]
Each string appears in its own group.
Case 5: Duplicate Strings
Input: ["eat", "tea", "eat", "ate"] Output: [[eat, tea, eat, ate]]
Duplicate strings are preserved because the task is to group anagrams, not remove duplicates.
Case 6: Empty Strings
Input: ["", "a", ""] Output: [["", ""], ["a"]]
Two empty strings are anagrams because both contain zero characters.
The sorting-based implementation handles empty strings because sorting an empty character array produces an empty grouping key.
Case 7: Uppercase and Lowercase Letters
Input: ["Eat", "tea", "ate"] Output: [[Eat], [tea, ate]]
By default, the sorting-based approach is case-sensitive.
Therefore, uppercase 'E' and lowercase 'e' are treated as different characters.
If you need case-insensitive grouping, normalize strings consistently before generating their keys.
Case 8: Null Strings
The implementations assume that every element in the input List is a non-null String.
Passing a null element causes a NullPointerException when the program calls toCharArray().
If null elements are possible in your application, either validate and reject them or define a separate rule for grouping null values.
9. Common Mistakes to Avoid
Mistake 1: Comparing Strings Only by Their Length
Two strings having the same length does not mean they are anagrams.
For example, "abc" and "xyz" have equal lengths but contain different characters.
You must compare their sorted characters or their character frequencies.
Mistake 2: Using an Ambiguous Frequency Key
When generating a key from character frequencies, avoid concatenating counts without separators.
For example, count sequences [1, 11] and [11, 1] could both produce the same text if you simply concatenate their values.
Use a separator or another unambiguous representation.
Mistake 3: Forgetting to Create a New List for Each Group
Each distinct anagram key must have its own List.
The computeIfAbsent() method makes this easy by creating a List only when the key is missing.
Mistake 4: Assuming HashMap Preserves Group Order
HashMap does not guarantee iteration order.
If your program needs predictable group order, use LinkedHashMap or explicitly sort the result.
Mistake 5: Assuming Character Frequency Works for Every Input
An integer array of length 26 supports only lowercase English letters when indexed using ch - 'a'.
Uppercase letters and other characters may produce invalid indexes.
Use the sorting-based approach when the input character set is not restricted to lowercase English letters.
10. Frequently Asked Questions
Q1. What is the group anagrams problem in Java?
The group anagrams problem asks you to organize a List of strings so that strings containing the same characters with identical frequencies belong to the same group.
Q2. What is the easiest way to group anagrams in Java?
One of the easiest approaches is to sort each string's characters and use the sorted result as a key in a HashMap.
Q3. Why is HashMap used for grouping anagrams?
HashMap efficiently associates a grouping key with a List of matching strings. Strings that produce the same key are added to the same group.
Q4. Can I group anagrams without sorting the strings?
Yes. For lowercase English letters, you can count the frequency of each character and use the resulting frequency representation as the key.
Q5. What is the time complexity of grouping anagrams using sorting?
The expected time complexity is O(n × k log k), where n is the number of strings and k is the maximum string length.
Q6. What is the time complexity of the frequency-based approach?
For lowercase English letters, the expected time complexity is O(n × (k + 26)), commonly simplified to O(n × k).
Q7. Does the order of anagram groups matter?
Most versions of the coding interview problem accept groups in any order. However, you should check the requirements of the specific problem.
Q8. Do duplicate strings remain in the result?
Yes. The provided programs preserve duplicate strings and place them in their corresponding anagram groups.
Q9. Which solution is better for Java coding interviews?
The sorting-based approach is generally the best starting point because it is simple and works for a broad range of string inputs.
The frequency-based approach is a useful optimization when the input is restricted to lowercase English letters.
11. Conclusion
In this tutorial, you learned how to group anagrams from a List of strings in Java using two different approaches.
- Sorting with HashMap: Sorts the characters of each string and groups strings that produce identical sorted keys.
- Character frequency with HashMap: Creates a frequency-based key without sorting, making it efficient for lowercase English-letter inputs.
For Java coding interviews, I recommend learning the sorting-based solution first. It is straightforward to implement, easy to explain, and demonstrates how HashMap can organize related data efficiently.
Once you understand the basic approach, practice the frequency-based solution. It helps you recognize an important optimization: when the character set is limited, counting character occurrences can be more efficient than sorting.
The same techniques are useful in other Java interview problems involving string anagrams, character frequency counting, duplicate detection, and HashMap-based grouping.
12. Official Java Documentation
For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:
- Java HashMap Class — Documentation for storing key-value mappings.
- Java LinkedHashMap Class — Documentation for predictable insertion-order iteration.
- Java Map Interface — Includes the
computeIfAbsent()method. - Java Arrays Class — Documentation for
Arrays.sort(). - Java String Class — Documentation for string operations, including
toCharArray(). - Java StringBuilder Class — Documentation for building character-frequency keys.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment