Group Anagrams

In this approach, we are going to loop through every string in input strings array strs, then for every character in the string, count each character appearance and store that as key and the string as value in a List.

For example if the input strings array is strs= ["ate", "eat"].

• We will first initialize a HashMap to store the results.
  Java

  HashMap<HashMap<Character, Integer>, List<String>> result = new HashMap<>();

• In the first step, we go through the characters in string "ate" and prepare a HashMap<Character, Integer> where key is the character and number of times it appeared is the value.
  a-1
  t-1
  e-1
  we will store this key HashMap and the string as value in a List into result HashMap.
• In the next step, we go through the characters in string "eat" and prepare a HashMap<Character, Integer> where key is the character and number of times it appeared is the value, same as what we have done in above step
  e-1
  a-1
  t-1
  Now, this key already present in result HashMap, so we simply append it to the value List.
• Finally, we simply return all the values in the result HashMap.

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

public class GroupAnagrams {

    /* Using char -> count as key and value as List of strings, then group all strings who has same char -> count*/
    static List<List<String>> usingHashMapToStoreCharacterCount(String[] strs) {
        HashMap<HashMap<Character, Integer>, List<String>> result = new HashMap<>();
        for(String str: strs) {
            HashMap<Character, Integer> key = new HashMap<>();
            for(char c: str.toCharArray()) {
                key.merge(c, 1, Integer::sum);
            }
            result.merge(key, new ArrayList<>(List.of(str)), (oldVal, newVal) -> {
                oldVal.addAll(newVal);
                return oldVal;
            });
        }
        return new ArrayList<>(result.values());
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n * m) time where n is the input strings strs length and m is the average length of a string in that array since we are looping through characters of each string
Space complexity: O(n) since we are storing all input strings into a HashMap

This approach will be same as above one, the only differece is that, instead of using a HashMap to store each character and its count, we will be using a char array with size 26.

To get character filled into this array of size 26, we can get the position by doing character at position i - 'a', it returns 0 for 'a', 1 for 'b' and so on and 26 for 'z'.

Once the char array is filled with character position and its count, we will then convert this into a String using String.valueOf(char[] chars) and use this as key to group all anagrams who has the same key.

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

public class GroupAnagrams {

    /* This is same as above, instead of using HashMap as key, we will construct an array with char -> count
        and convert that to a string for e.g. abc will be [1, 1, 1, 0, 0, 0, 0, .........], it will become a
        string with 26 characters length 11100000000000....*/
    static List<List<String>> usingCharArrayAsKey(String[] strs) {
        HashMap<String, List<String>> result = new HashMap<>();
        for (String str : strs) {
            char[] count = new char[26];
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }
            result.merge(String.valueOf(count), new ArrayList<>(List.of(str)), (oldVal, newVal) -> {
                oldVal.addAll(newVal);
                return oldVal;
            });
        }
        return  new ArrayList<>(result.values());

    }


}

Complexity Analysis:

Time complexity: Above code runs in O(n * m) time where n is the input strings strs length and m is the average length of a string in that array since we are looping through characters of each string
Space complexity: O(n) since we are storing all input strings into a HashMap