Algorithm-Day02-Group-Anagrams-lc#49

🧩 Problem Description

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 original letters exactly once.

Example:

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

💡 Approach

🔸 Idea

Two strings are anagrams if their sorted character arrays are the same.

So we can:

• Sort each string.
• Use a hash map to group original strings by their sorted version.

🔧 Why Hash Table?

The sorted string acts as a unique key for anagram groups.
We use a Map<String, List<String>> to group anagrams efficiently.

🔢 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); // sorted string

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

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

⏱ Time and Space Complexity

• Time Complexity: O(n * k log k)
  • n = number of strings
  • k = max length of a string (due to sorting)
• Space Complexity: O(n * k)
  • To store grouped anagrams in a hash map

✍️ Summary

• Key idea: Use the sorted string as hash map key.
• Efficient and elegant hash table application.
• Classic grouping problem using Java Map and sorting.