Group Anagrams - Complete Java Solutions Guide
Problem Statement
Given an array of strings strs , group the anagrams together. You can return the answer in any
order.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [[""]]
Example 3:
Input: strs = ["a"]
Output: [["a"]]
Approach 1: Brute Force with Nested Loops
Algorithm
Compare each string with every other string to check if they are anagrams by sorting characters.
Time Complexity: O(n² × m log m)
n = number of strings, m = average length of strings
For each pair, we sort characters which takes O(m log m)
Space Complexity: O(n × m)
Storage for result groups
java
import [Link].*;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
boolean[] used = new boolean[[Link]];
for (int i = 0; i < [Link]; i++) {
if (used[i]) continue;
List<String> group = new ArrayList<>();
[Link](strs[i]);
used[i] = true;
// Find all anagrams of strs[i]
for (int j = i + 1; j < [Link]; j++) {
if (!used[j] && areAnagrams(strs[i], strs[j])) {
[Link](strs[j]);
used[j] = true;
}
}
[Link](group);
}
return result;
}
private boolean areAnagrams(String s1, String s2) {
if ([Link]() != [Link]()) return false;
char[] arr1 = [Link]();
char[] arr2 = [Link]();
[Link](arr1);
[Link](arr2);
return [Link](arr1, arr2);
}
}
Pros:
Simple to understand and implement
No additional data structures needed
Cons:
Very inefficient for large inputs
Redundant comparisons
High time complexity
Approach 2: HashMap with Sorted String as Key
Algorithm
Use sorted characters of each string as a key in HashMap to group anagrams.
Time Complexity: O(n × m log m)
n = number of strings, m = average length of strings
Sorting each string takes O(m log m)
Space Complexity: O(n × m)
HashMap storage
java
import [Link].*;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> anagramMap = new HashMap<>();
for (String str : strs) {
// Sort the string to create a key
char[] charArray = [Link]();
[Link](charArray);
String sortedKey = new String(charArray);
// Add to the group
[Link](sortedKey, k -> new ArrayList<>()).add(str)
}
return new ArrayList<>([Link]());
}
}
Alternative Implementation with Manual Key Creation:
java
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
String key = getSortedKey(str);
if () {
[Link](key, new ArrayList<>());
}
[Link](key).add(str);
}
return new ArrayList<>([Link]());
}
private String getSortedKey(String str) {
char[] chars = [Link]();
[Link](chars);
return new String(chars);
}
}
Pros:
Much more efficient than brute force
Clean and readable code
Handles duplicates naturally
Cons:
Still requires O(m log m) sorting for each string
Approach 3: HashMap with Character Frequency as Key
Algorithm
Use character frequency count as key instead of sorting. This avoids the O(m log m) sorting
cost.
Time Complexity: O(n × m)
n = number of strings, m = average length of strings
Counting characters takes O(m) per string
Space Complexity: O(n × m)
HashMap storage plus frequency arrays
java
import [Link].*;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> anagramMap = new HashMap<>();
for (String str : strs) {
String frequencyKey = getFrequencyKey(str);
[Link](frequencyKey, k -> new ArrayList<>()).add(s
}
return new ArrayList<>([Link]());
}
private String getFrequencyKey(String str) {
int[] frequency = new int[26]; // For lowercase letters a-z
for (char c : [Link]()) {
frequency[c - 'a']++;
}
// Convert frequency array to string
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (frequency[i] > 0) {
[Link]((char)('a' + i)).append(frequency[i]);
}
}
return [Link]();
}
}
Alternative with [Link]():
java
private String getFrequencyKey(String str) {
int[] frequency = new int[26];
for (char c : [Link]()) {
frequency[c - 'a']++;
}
return [Link](frequency);
}
Pros:
Better time complexity O(n × m) vs O(n × m log m)
More efficient for longer strings
No sorting required
Cons:
Slightly more complex implementation
Key string might be longer
Approach 4: Optimal - Prime Number Encoding (Mathematical Approach)
Algorithm
Assign each character a unique prime number and use the product as the key. Since anagrams
have the same characters, they'll have the same product.
Time Complexity: O(n × m)
n = number of strings, m = average length of strings
Space Complexity: O(n × m)
HashMap storage
java
import [Link].*;
public class Solution {
// Prime numbers for each letter a-z
private static final int[] PRIMES = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
};
public List<List<String>> groupAnagrams(String[] strs) {
Map<Long, List<String>> anagramMap = new HashMap<>();
for (String str : strs) {
long primeProduct = getPrimeProduct(str);
[Link](primeProduct, k -> new ArrayList<>()).add(s
}
return new ArrayList<>([Link]());
}
private long getPrimeProduct(String str) {
long product = 1;
for (char c : [Link]()) {
product *= PRIMES[c - 'a'];
}
return product;
}
}
With Overflow Protection:
java
import [Link];
public class Solution {
private static final int[] PRIMES = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
};
public List<List<String>> groupAnagrams(String[] strs) {
Map<BigInteger, List<String>> anagramMap = new HashMap<>();
for (String str : strs) {
BigInteger primeProduct = getPrimeProduct(str);
[Link](primeProduct, k -> new ArrayList<>()).add(s
}
return new ArrayList<>([Link]());
}
private BigInteger getPrimeProduct(String str) {
BigInteger product = [Link];
for (char c : [Link]()) {
product = [Link]([Link](PRIMES[c - 'a']));
}
return product;
}
}
Pros:
Very fast O(n × m) time complexity
Mathematically elegant
Unique encoding for each anagram group
Cons:
Risk of integer overflow for very long strings
Uses more memory for BigInteger approach
Limited to specific character sets
Approach 5: Greedy Optimized with Early Termination
Algorithm
Combines frequency counting with early termination optimizations and preprocessing.
Time Complexity: O(n × m) average case, better with optimizations
Space Complexity: O(n × m)
java
import [Link].*;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs == null || [Link] == 0) {
return new ArrayList<>();
}
// Preprocess: sort by length for better cache locality
Map<Integer, List<String>> lengthGroups = new HashMap<>();
for (String str : strs) {
[Link]([Link](), k -> new ArrayList<>()).add
}
List<List<String>> result = new ArrayList<>();
// Process each length group separately
for (List<String> lengthGroup : [Link]()) {
[Link](groupAnagramsByLength(lengthGroup));
}
return result;
}
private List<List<String>> groupAnagramsByLength(List<String> strs) {
Map<String, List<String>> anagramMap = new HashMap<>();
for (String str : strs) {
String key = getOptimizedKey(str);
[Link](key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>([Link]());
}
private String getOptimizedKey(String str) {
// Use byte array for smaller memory footprint
int[] count = new int[26];
for (int i = 0; i < [Link](); i++) {
count[[Link](i) - 'a']++;
}
// Create compact key representation
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
[Link]((char)('a' + i)).append(count[i]);
}
}
return [Link]();
}
}
Advanced Greedy with Rolling Hash:
java
public class Solution {
private static final int BASE = 31;
private static final int MOD = 1000000007;
public List<List<String>> groupAnagrams(String[] strs) {
Map<Long, List<String>> anagramMap = new HashMap<>();
for (String str : strs) {
long hash = getRollingHash(str);
[Link](hash, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>([Link]());
}
private long getRollingHash(String str) {
long hash = 0;
long[] charHashes = new long[26];
// Calculate individual character hashes
for (int i = 0; i < 26; i++) {
charHashes[i] = ((long) [Link](BASE, i + 1)) % MOD;
}
// Sum hashes for all characters (order independent)
for (char c : [Link]()) {
hash = (hash + charHashes[c - 'a']) % MOD;
}
return hash;
}
}
Performance Comparison
Approach Time Complexity Space Complexity Best For
Brute Force O(n² × m log m) O(n × m) Small inputs
Sorted Key O(n × m log m) O(n × m) General use
Frequency Key O(n × m) O(n × m) Large strings
Prime Encoding O(n × m) O(n × m) Performance critical
Greedy Optimized O(n × m) O(n × m) Production systems
Recommended Solution
For most practical purposes, Approach 3 (Character Frequency) is recommended because:
1. Optimal time complexity O(n × m)
2. Simple and readable code
3. No overflow risks unlike prime encoding
4. Memory efficient compared to sorting approach
5. Handles all edge cases reliably
java
// Final Recommended Solution
import [Link].*;
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> anagramMap = new HashMap<>();
for (String str : strs) {
String key = getFrequencyKey(str);
[Link](key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>([Link]());
}
private String getFrequencyKey(String str) {
int[] frequency = new int[26];
for (char c : [Link]()) {
frequency[c - 'a']++;
}
return [Link](frequency);
}
}
Test Cases
java
public class TestGroupAnagrams {
public static void main(String[] args) {
Solution solution = new Solution();
// Test Case 1
String[] test1 = {"eat","tea","tan","ate","nat","bat"};
[Link]("Test 1: " + [Link](test1));
// Test Case 2
String[] test2 = {""};
[Link]("Test 2: " + [Link](test2));
// Test Case 3
String[] test3 = {"a"};
[Link]("Test 3: " + [Link](test3));
// Test Case 4 - Edge case
String[] test4 = {"abc", "bca", "cab", "xyz", "zyx", "yxz"};
[Link]("Test 4: " + [Link](test4));
}
}
This comprehensive guide covers all major approaches from basic to optimal solutions for the
Group Anagrams problem in Java.