LeetCode Problem 49: Group Anagrams – Java Solution Using HashMap and Sorting

Looking for an elegant solution to group anagrams in Java? LeetCode Problem 49: Group Anagrams is a classic string manipulation problem frequently asked in coding interviews. In this guide, we’ll walk through a simple and effective approach using HashMaps and string sorting to group words that are anagrams of each other.

Problem Overview

You’re given an array of strings strs, and your goal is to group the words that are anagrams of each other.

An anagram is formed by rearranging the letters of a word — for example, "listen" and "silent".

Example:

Input:
["eat","tea","tan","ate","nat","bat"]
Output:
[["bat"],["nat","tan"],["eat","tea","ate"]]

Strategy: Sort + HashMap

Core Idea:

Anagrams share the same sorted character sequence.
For example:

• "eat", "tea", "ate" all become "aet" when sorted.

Steps:

1. Sort each string to get a standardized form.
2. Use a HashMap to group strings by their sorted form.
3. Return the grouped values from the map.

Java Code

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);

            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
}

How the Code Works

1. Create a HashMap where:
   • Key = sorted version of the string (e.g., "aet")
   • Value = list of original strings (anagrams)
2. Loop through each string, sort it, and use the result as the key.
3. Group the original strings into lists under their respective keys.
4. Return all the values from the HashMap — each list is a group of anagrams.

Complexity Analysis

• Time Complexity:O(N × K log K)
  • N = number of strings, K = max string length
  • Sorting each string takes O(K log K)
• Space Complexity:O(N × K)
  • Stores all input strings grouped by their sorted key

Key Concepts

• Sorting is the key: It transforms anagrams into identical representations.
• HashMap allows fast grouping: Lookup and insert operations are constant time on average.
• Efficient and readable: This approach balances performance and code simplicity.

FAQs

Q1: Can we avoid sorting to improve performance?
Yes, using a character count array (e.g., "a1b0c2...") as the key can reduce time to O(N × K), but it’s more complex to implement.

Q2: What if the input contains non-lowercase or Unicode characters?
Java’s Arrays.sort() works with all characters, including Unicode.

Q3: Will this work for empty strings or single-character words?
Absolutely. Those are grouped just like any other word.

Q4: Does output order matter?
No. The problem allows returning the groups in any order.

Related LeetCode Problems

• Valid Anagram (LeetCode 242) – Check if two strings are anagrams
• Group Shifted Strings (LeetCode 249) – Group strings shifted by the same pattern
• Find All Anagrams in a String (LeetCode 438) – Use a sliding window to detect anagrams

Real-Life Applications

• Word Games: Like Scrabble, Boggle, or auto-suggestion tools
• Search Optimization: Group similar queries or misspelled terms
• Security: Identify obfuscated phishing domains using anagram patterns

Wrap-Up:
Now that you understand how to group anagrams using sorting and HashMaps in Java, try implementing it on your own. Practice with different inputs, explore alternative approaches like frequency maps, and dive deeper into string manipulation problems to sharpen your skills!