Problem Statement

You are given an array of strings strs. The task is to group the strings that are anagrams of each other.

Definition: Two strings are anagrams if they have the same characters in the same frequency but possibly in a different order.

Example:

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

Constraints:

1. All inputs are lowercase letters.
2. Order of the output groups or the strings inside a group does not matter.

Approach

The main idea is to use a hash map to group strings by a unique key that identifies anagrams. There are two common ways to generate such a key:

Method 1: Sorting

• For each string, sort its characters alphabetically.
• Use the sorted string as a key in a hash map.
• All strings with the same sorted characters are anagrams and will map to the same key.

Example:

• "eat" → sorted → "aet"
• "tea" → sorted → "aet"
• "tan" → sorted → "ant"

So the map will look like:

"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]

Method 2: Character Count (Optimized)

• Count the frequency of each character in the string.
• Convert the count into a string key (e.g., "a1e1t1" for "eat").
• This avoids the sorting step and can be faster for longer strings.

Example:

• "eat" → count → [1,0,0,...,1,...,1,...] → "1,0,0,...,1,...,1,..."
• "tea" → same count → same key

Java Implementation (Sorting Method)

import java.util.*;

public class GroupAnagrams {

    public static 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[] chars = s.toCharArray();
            Arrays.sort(chars);                  // sort characters
            String key = new String(chars);      // convert sorted char array to string

            // add string to the list for this key
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }

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

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = groupAnagrams(input);
        System.out.println(result);
    }
}

Output:

[[eat, tea, ate], [tan, nat], [bat]]

Java Implementation (Character Count Method)

import java.util.*;

public class GroupAnagramsOptimized {

    public static 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) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count++;
            }

            // convert count array to string key
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#');       // delimiter to avoid ambiguity
                sb.append(count[i]);
            }
            String key = sb.toString();

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

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

    public static void main(String[] args) {
        String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = groupAnagrams(input);
        System.out.println(result);
    }
}

Advantages:

• Sorting method: simple and easy to understand.
• Count method: faster for long strings (O(NK)) instead of O(NK*logK) for sorting, where K is string length.

Key Points:

1. HashMap is the core data structure for grouping anagrams.
2. Sorting strings or counting characters generates a unique key for each anagram group.
3. Use List<List<String>> to return the grouped anagrams.
4. computeIfAbsent is a convenient Java 8+ method to initialize lists in a map.