Group Anagrams

We are provided with an array of strings, strs, and our objective is to group the anagrams together. The order of the output can be arbitrary.

An anagram is a term created by rearranging the characters of another word or phrase, often utilizing each original letter exactly once.

Example 1

Given an array of strings, strs = ["eat", "tea", "tan", "ate", "nat", "bat"], the grouped anagrams are [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]].

Example 2

For the input strs = [""], the resulting grouped anagrams are [[""]].

Example 3

In the case of strs = ["a"], the grouped anagrams consist of [["a"]].

Idea

The problem of grouping anagrams involves categorizing a list of strings into groups where each group contains strings that are anagrams of each other. Anagrams are words or phrases formed by rearranging the letters of another.

To solve this problem efficiently, you can use a HashMap to keep track of the groups of anagrams. The key to solving this problem is to recognize that anagrams will have the same sorted characters. Therefore, you can use the sorted characters of each string as a key in the HashMap.

Algorithm

1. Create an empty HashMap where the key will be the sorted representation of an anagram, and the value will be a list of strings belonging to that group of anagrams.
2. Iterate through the array of strings.
3. For each string in the array:
   1. Convert the string into a character array. Sort the character array, turning it into a sorted string. This step ensures that anagrams will have the same sorted representation.
4. Check if the sorted string exists as a key in the HashMap. If it doesn't exist, add it as a new key with an empty list as the initial value.
5. Add the original string to the list corresponding to the sorted string in the HashMap. This groups anagrams together.
6. After processing all the strings, the HashMap will contain keys for each unique sorted representation of anagrams and values that are lists of grouped anagrams.
7. Return the values of the HashMap as the final result, which will be a list of lists, each containing grouped anagrams.

Complexity

• Time Complexity: O(n * k * log(k)), where 'n' is the number of strings, and 'k' is the maximum length of a string in the input.
• Space Complexity: O(n), where 'n' is the number of strings

Java Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);

            // Use computeIfAbsent to simplify adding new entries to the map
            anagramMap.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
        }

        // Return the values (lists of anagrams) from the map
        return new ArrayList<>(anagramMap.values());
    }

    public static void main(String[] args) {
        GroupAnagrams groupAnagrams = new GroupAnagrams();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> groupedAnagrams = groupAnagrams.groupAnagrams(strs);

        System.out.println("Grouped Anagrams:");
        for (List<String> group : groupedAnagrams) {
            System.out.println(group);
        }
    }
}

Output

Grouped Anagrams:

[eat, tea, ate]

[bat]

[tan, nat]