Group Anagrams problem and solution in Java and Python

Let’s go through the Group Anagrams problem — one of the most common interview questions that builds on the Valid Anagram concept.

---

🧩 Problem: Group Anagrams

Question: Given an array of strings, group the anagrams together.

Example:

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

---

💡 Intuition

An anagram group means all words that have the same set of letters.

For example:

• "eat", "tea", "ate" → all can be rearranged to "aet" So, their sorted version is the same → "aet"

If two words have the same sorted version, they belong to the same group.

---

🪜 Approach 1 — Sorting Based Key (Most Common)

🧠 Idea:

• Sort every word alphabetically.
• Use the sorted word as a key in a HashMap.
• Add the original word into the group (value list) for that key.

Example:

Word	Sorted Key	Groups
eat	aet	["eat"]
tea	aet	["eat","tea"]
tan	ant	["tan"]
ate	aet	["eat","tea","ate"]
nat	ant	["tan","nat"]
bat	abt	["bat"]

---

✅ Java Solution

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            char[] ch = s.toCharArray();
            Arrays.sort(ch);
            String key = new String(ch);  // e.g. "aet"
            
            if (!map.containsKey(key))
                map.put(key, new ArrayList<>());
            
            map.get(key).add(s);
        }
        
        return new ArrayList<>(map.values());
    }
}

---

✅ Python Solution

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    
    for word in strs:
        key = ''.join(sorted(word))
        groups[key].append(word)
    
    return list(groups.values())

---

🧠 Approach 2 — Character Count Key (Optimized)

Sorting each string takes O(k log k) time. If strings are long but have limited characters (like lowercase English letters), we can count characters instead.

---

⚙️ Idea

• Create an array of length 26 for each word.
• Use character counts as a key.

Example: "eat" → [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0] "tea" → same key → group together!

---

✅ Java Solution (Counting)

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            String key = Arrays.toString(count);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

---

✅ Python Solution (Counting)

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    
    for word in strs:
        count = [0] * 26
        for c in word:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(word)
    
    return list(groups.values())

---

⚖️ Complexity

Approach	Time Complexity	Space Complexity	Notes
Sorting key	O(n * k log k)	O(n * k)	Easy and clean
Count key	O(n * k)	O(n * k)	Faster for long strings

---

🌍 Real-World Analogy

Imagine a dictionary shelf 🧾:

• Each shelf is labeled by the sorted letters.
• Any word that matches those letters goes on that shelf. So "tea", "ate", "eat" all go on the "aet" shelf!

---