10. Group Anagrams

🔗 LeetCode Problem: 49. Group Anagrams
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, String, Sorting

Problem Statement

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Explanation:
- "eat", "tea", "ate" are anagrams (same letters)
- "tan", "nat" are anagrams
- "bat" is alone

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints: - 1 <= strs.length <= 10^4 - 0 <= strs[i].length <= 100 - strs[i] consists of lowercase English letters

---

🎨 Visual Understanding

The Problem Visualized

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

Anagram Groups:
Group 1: "eat", "tea", "ate"
         e-a-t  t-e-a  a-t-e  ← Same letters, different order

Group 2: "tan", "nat"
         t-a-n  n-a-t  ← Same letters, different order

Group 3: "bat"
         b-a-t  ← Unique letters

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

How to Identify Anagrams?

Two strings are anagrams if:
1. Same length
2. Same characters
3. Same frequency of each character

Methods to identify:
Method 1: Sort both strings
  "eat" → sort → "aet"
  "tea" → sort → "aet"
  Same sorted form → anagrams! ✓

Method 2: Count character frequency
  "eat" → {e:1, a:1, t:1}
  "tea" → {t:1, e:1, a:1}
  Same counts → anagrams! ✓

Grouping Strategy

Use HashMap with signature as key:

Signature = sorted string OR frequency pattern

HashMap structure:
{
  "aet": ["eat", "tea", "ate"],
  "ant": ["tan", "nat"],
  "abt": ["bat"]
}

Then extract values to get groups:
[["eat","tea","ate"], ["tan","nat"], ["bat"]]

---

🎯 Approach 1: Sorting as Key

The Most Natural Thinking 💭

Core Logic:

Use sorted string as the signature/key:

For each string:
1. Sort the characters
2. Use sorted string as HashMap key
3. Add original string to that key's list

Example:
  "eat" → sort → "aet" → map["aet"].add("eat")
  "tea" → sort → "aet" → map["aet"].add("tea")
  "tan" → sort → "ant" → map["ant"].add("tan")

Finally, return all values from HashMap

Why This Works:

• Anagrams have identical sorted forms
• HashMap groups strings with same sorted form
• Simple and intuitive approach

Trade-off:

• Sorting each string costs O(k log k) where k = string length
• Total time: O(n × k log k)

Implementation

public List<List<String>> groupAnagrams(String[] strs) {
    // HashMap: sorted string → list of anagrams
    HashMap<String, List<String>> map = new HashMap<>();

    for (String str : strs) {
        // Sort the string to create key
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        // Add to corresponding group
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(str);
    }

    // Return all groups
    return new ArrayList<>(map.values());
}

Step-by-Step Execution: strs = ["eat","tea","tan","ate","nat","bat"]

Initial: map = {}

Process "eat":
├─ Sort: "eat" → ['e','a','t'] → sort → ['a','e','t'] → "aet"
├─ Key: "aet"
├─ map["aet"] doesn't exist → create new list
└─ map = {"aet": ["eat"]}

Process "tea":
├─ Sort: "tea" → ['t','e','a'] → sort → ['a','e','t'] → "aet"
├─ Key: "aet"
├─ map["aet"] exists → add to existing list
└─ map = {"aet": ["eat", "tea"]}

Process "tan":
├─ Sort: "tan" → ['t','a','n'] → sort → ['a','n','t'] → "ant"
├─ Key: "ant"
├─ map["ant"] doesn't exist → create new list
└─ map = {"aet": ["eat","tea"], "ant": ["tan"]}

Process "ate":
├─ Sort: "ate" → ['a','t','e'] → sort → ['a','e','t'] → "aet"
├─ Key: "aet"
├─ map["aet"] exists → add to existing list
└─ map = {"aet": ["eat","tea","ate"], "ant": ["tan"]}

Process "nat":
├─ Sort: "nat" → ['n','a','t'] → sort → ['a','n','t'] → "ant"
├─ Key: "ant"
├─ map["ant"] exists → add to existing list
└─ map = {"aet": ["eat","tea","ate"], "ant": ["tan","nat"]}

Process "bat":
├─ Sort: "bat" → ['b','a','t'] → sort → ['a','b','t'] → "abt"
├─ Key: "abt"
├─ map["abt"] doesn't exist → create new list
└─ map = {"aet": ["eat","tea","ate"], "ant": ["tan","nat"], "abt": ["bat"]}

Final map:
═══════════════════════════════════════════════════════════════════
{
  "aet": ["eat", "tea", "ate"],
  "ant": ["tan", "nat"],
  "abt": ["bat"]
}

Return map.values():
[["eat","tea","ate"], ["tan","nat"], ["bat"]]
═══════════════════════════════════════════════════════════════════

⏰ Time: O(n × k log k) where n = number of strings, k = max string length
💾 Space: O(n × k) - store all strings in HashMap

---

✅ Approach 2: Character Count as Key (Optimal)

The Breakthrough Insight 💡

Core Logic:

Instead of sorting (O(k log k)), use character frequency as signature!

For each string:
1. Count frequency of each character
2. Create a unique key from frequency
3. Use as HashMap key

Key generation:
  "eat" → [1,0,0,0,1,0,...,1,0,...0] (26 positions for a-z)
         OR
  "eat" → "#1#0#0#0#1#0...#1#0...#0" (string representation)

Why this is better:
- Counting is O(k) vs sorting O(k log k)
- Same anagrams produce same frequency signature

Character Count Array Representation:

"eat" has:
  'a' appears 1 time → count[0] = 1
  'e' appears 1 time → count[4] = 1
  't' appears 1 time → count[19] = 1

Convert to string key: "1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0"

"tea" produces same key → grouped together!

Why This is Better: - O(k) to count characters vs O(k log k) to sort - Total time: O(n × k) instead of O(n × k log k) - More efficient for longer strings

Implementation

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

    for (String str : strs) {
        // Count character frequencies
        int[] count = new int[26];
        for (char c : str.toCharArray()) {
            count[c - 'a']++;
        }

        // Build key from frequency array
        StringBuilder keyBuilder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            keyBuilder.append('#');
            keyBuilder.append(count[i]);
        }
        String key = keyBuilder.toString();

        // Add to corresponding group
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(str);
    }

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

Step-by-Step Execution: strs = ["eat","tea","tan"]

Process "eat":
═══════════════════════════════════════════════════════════════════
Step 1: Count characters
  count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
           a b c d e f g h i j k l m n o p q r s t u v w x y z

  'e' → count[4]++  → count[4] = 1
  'a' → count[0]++  → count[0] = 1
  't' → count[19]++ → count[19] = 1

  count = [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]

Step 2: Build key
  key = "#1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0"

Step 3: Add to map
  map[key] = ["eat"]


Process "tea":
═══════════════════════════════════════════════════════════════════
Step 1: Count characters
  't' → count[19] = 1
  'e' → count[4] = 1
  'a' → count[0] = 1

  count = [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]

Step 2: Build key
  key = "#1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0"
  (Same as "eat"!)

Step 3: Add to map
  map[key] = ["eat", "tea"]


Process "tan":
═══════════════════════════════════════════════════════════════════
Step 1: Count characters
  't' → count[19] = 1
  'a' → count[0] = 1
  'n' → count[13] = 1

  count = [1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0]

Step 2: Build key
  key = "#1#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#1#0#0#0#0#0#0"
  (Different key!)

Step 3: Add to map
  map[key] = ["tan"]


Final Result:
═══════════════════════════════════════════════════════════════════
map = {
  "#1#0#0#0#1#0...#1#0...": ["eat", "tea"],
  "#1#0#0#0#0#0...#1#0...": ["tan"]
}

Return: [["eat","tea"], ["tan"]]

⏰ Time: O(n × k) where n = number of strings, k = max string length
💾 Space: O(n × k) - store all strings in HashMap

---

🔍 Edge Cases

Case 1: Empty string
Input: [""]
Output: [[""]]
Strategy: Empty string groups with itself

Case 2: Single string
Input: ["a"]
Output: [["a"]]

Case 3: No anagrams (all unique)
Input: ["abc", "def", "ghi"]
Output: [["abc"], ["def"], ["ghi"]]
Strategy: Each string in its own group

Case 4: All anagrams
Input: ["abc", "bca", "cab"]
Output: [["abc","bca","cab"]]
Strategy: All in one group

Case 5: Single character strings
Input: ["a", "b", "a", "c", "b"]
Output: [["a","a"], ["b","b"], ["c"]]

Case 6: Different length strings (can't be anagrams)
Input: ["ab", "abc", "ba"]
Output: [["ab","ba"], ["abc"]]

Case 7: Strings with repeated characters
Input: ["aaa", "aaa", "aa"]
Output: [["aaa","aaa"], ["aa"]]

Case 8: Large input (10,000 strings)
Input: 10,000 strings
Output: Grouped efficiently
Strategy: HashMap handles large inputs well

---

Common Mistakes

Mistake 1: Not handling empty strings
❌ Wrong: Assume all strings non-empty
✓ Right: Empty string is valid input

Mistake 2: Using array as HashMap key directly
❌ Wrong: map.put(count, list); // int[] as key doesn't work
✓ Right: Convert to String first

Mistake 3: Wrong frequency encoding
❌ Wrong: "111" for [1,1,1] → conflicts with [11,1] or [1,11]
✓ Right: Use delimiter "#1#1#1"

Mistake 4: Comparing with == for strings
❌ Wrong: if (sorted1 == sorted2)
✓ Right: if (sorted1.equals(sorted2))

Mistake 5: Not initializing ArrayList for new keys
❌ Wrong: map.get(key).add(str); // NullPointerException
✓ Right: map.putIfAbsent(key, new ArrayList<>());

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Sorting as Key
  Time: O(n × k log k)
  Space: O(n × k)
  Use: Simple, easy to code

Approach 2: Character Count as Key (OPTIMAL)
  Time: O(n × k)
  Space: O(n × k)
  Use: Faster, optimal solution

🔑 The Core Insight

Anagrams have same character frequency!

Two ways to create signature:
1. Sort string → O(k log k) per string
2. Count frequency → O(k) per string

Character count is faster:
→ Create frequency array (26 elements for a-z)
→ Convert to string as HashMap key
→ Group strings with same key

Pattern: Signature-based grouping with HashMap

🎯 Pattern Recognition

Problem Type: Grouping by Equivalence
Core Pattern: HashMap with signature key

When to Apply:
✓ Need to group items by some property
✓ Property can be computed for each item
✓ Order within groups doesn't matter
✓ Multiple items can share same property

Key Techniques:
→ Signature function (sorted string or frequency)
→ HashMap for grouping
→ Convert signature to string (for HashMap key)

Related Problems:
- Valid Anagram (LC 242)
- Find All Anagrams in String (LC 438)
- Isomorphic Strings (LC 205)
- Group Shifted Strings (LC 249)

🧠 Interview Strategy

Step 1: "Need to group strings that are anagrams"
Step 2: "Anagrams have same letters with same frequency"
Step 3: "Can use sorted string as key - O(n × k log k)"
Step 4: "Better: use character count - O(n × k)"
Step 5: "HashMap groups strings with same signature"

---

📝 Quick Revision Notes

🎯 Core Concept:

Group anagrams using HashMap with signature as key. Signature can be sorted string or character frequency pattern.

⚡ Quick Implementation:

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> res = new ArrayList<>();

    // // Approach 1 - sort chars of each string
    // Map<String, ArrayList<String>> map = new HashMap<>();
    // for(String s : strs) {
    //     // Get sorted string by sorting the chars of each string
    //     // If they are anagrams, the sorted string would be the same
    //     // We will add that sorted string as map key (kind of a hash) and add actual string in the list that the key holds.
    //     char[] ch = s.toCharArray();
    //     Arrays.sort(ch);
    //     String sorted = new String(ch);

    //     // Put the sorted string as key and add actual value to the list
    //     if(!map.containsKey(sorted)) {
    //         map.put(sorted, new ArrayList<>());
    //     }

    //     map.get(sorted).add(s);
    // }

    // Approach 2 - create a custom hash
    Map<String, ArrayList<String>> map = new HashMap<>();
    for(String s : strs) {
        // freq count of chars
        int[] freq = new int[26];
        for(char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        // create a custom hash
        StringBuilder sb = new StringBuilder();
        for(int count : freq) {
            sb.append("#").append(count);
        }

        // Now add to the map.
        if(!map.containsKey(sb.toString())) {
            map.put(sb.toString(), new ArrayList<>());
        }

        map.get(sb.toString()).add(s);
    }

    for(String key : map.keySet()) {
        ArrayList<String> temp = new ArrayList<>();
        temp.addAll(map.get(key));
        res.add(temp);
    }

    return res;
}

🔑 Key Insights:

• Anagrams have identical sorted forms
• HashMap groups by signature
• Sorting: O(k log k) per string
• Frequency count: O(k) per string (optimal)
• Use delimiter in frequency encoding (#1#2#3)
• Return map.values() to get all groups

🎪 Memory Aid:

"Sort or count, use as key, group together!"
Think: "Same signature → same group in HashMap"

---

Related Patterns

• Valid Anagram (LC 242)
• Find All Anagrams in String (LC 438)
• Group Shifted Strings (LC 249)

---

Happy practicing! 🎯