4. Group Anagrams

Here’s a progression from brute force to the most optimal solution for the Group Anagrams problem, focusing on time complexity and implementation improvements.

---

Problem Statement:

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

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

Output:

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

---

Approach 1: Brute Force (O(n² * k log k))

Steps:

1. Iterate through each word.
2. Compare it with every other word using sorting to check if they are anagrams.
3. If two words are anagrams, group them together.
4. Remove the grouped words from the input list to avoid redundant comparisons.

Code (Java):

import java.util.*;

public class GroupAnagramsBruteForce {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>(Arrays.asList("eat", "tea", "tan", "ate", "nat", "bat"));
        List<List<String>> result = new ArrayList<>();

        while (!words.isEmpty()) {
            String word = words.get(0);
            List<String> anagrams = new ArrayList<>();
            anagrams.add(word);
            words.remove(0);  // Remove the word we’re checking

            for (int i = 0; i < words.size(); i++) {
                if (areAnagrams(word, words.get(i))) {
                    anagrams.add(words.get(i));
                    words.remove(i);  // Remove the matched word and adjust index
                    i--;
                }
            }
            result.add(anagrams);
        }

        System.out.println(result);
    }

    // Function to check if two words are anagrams
    public static boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        return Arrays.equals(arr1, arr2);
    }
}

Time Complexity:

• Sorting a word: O(k log k)
• Nested loop: O(n²) comparisons
• Overall: O(n² * k log k)

---

Approach 2: Using Sorting and HashMap (O(n * k log k))

Steps:

1. Sort the characters of each word. The sorted version of any anagram will be the same.
2. Use a HashMap to group words based on their sorted string as the key.
3. Return all the grouped values from the HashMap.

Code (Java):

import java.util.*;

public class GroupAnagramsSorting {
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<String, List<String>> map = new HashMap<>();

        // Group words by their sorted version
        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);  // Sorting the word
            String sortedWord = new String(chars);

            map.putIfAbsent(sortedWord, new ArrayList<>());
            map.get(sortedWord).add(word);
        }

        List<List<String>> result = new ArrayList<>(map.values());
        System.out.println(result);
    }
}

Time Complexity:

• Sorting a word: O(k log k)
• Iterating through n words: O(n)
• Overall: O(n * k log k)
  (Much faster than the brute force approach!)

---

Approach 3: Optimal Solution Using Character Frequency (O(n * k))

Steps:

1. Instead of sorting the words, use a character frequency count as the key.

• For example, "eat" and "tea" will have the same frequency counts: {'e': 1, 'a': 1, 't': 1}.

1. Use an array of size 26 (for lowercase English letters) to store character frequencies.
2. Use the frequency array as a unique key (convert it to a string) to group anagrams.

Code (Java):

import java.util.*;

public class GroupAnagramsOptimal {
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        Map<String, List<String>> map = new HashMap<>();

        for (String word : words) {
            int[] count = new int[26];  // Character frequency array
            for (char c : word.toCharArray()) {
                count[c - 'a']++;  // Increment count based on character
            }

            // Convert the frequency array to a unique string key
            String key = Arrays.toString(count);

            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(word);
        }

        List<List<String>> result = new ArrayList<>(map.values());
        System.out.println(result);
    }
}

Time Complexity:

• Counting characters for each word: O(k)
• Iterating through n words: O(n)
• Overall: O(n * k)
  (Linear time solution!)

Space Complexity:

• O(n * k) to store the input words and frequency arrays in the map.

---

Summary of Approaches:

Approach	Time Complexity	Space Complexity	Explanation
1. Brute Force	O(n² * k log k)	O(n * k)	Compare each word with every other word
2. Sorting + HashMap	O(n * k log k)	O(n * k)	Group by sorted characters
3. Character Frequency + HashMap	O(n * k)	O(n * k)	Group by character frequency (most optimal)

---

Which Approach to Use?

• For small inputs: Any approach works fine.
• For large inputs: Use the character frequency-based solution (O(n * k)) for the best performance.

---