Group Anagrams

Example:

Given an array of strings, group anagrams together.

Example:

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

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

Algorithm:

1 For each new word in the given input list, use a hash array of size 26 and compute the frequency of each character occurring in that word.

2 Then using a StringBuilder, we can append the values in the hash array to potentially form a key in a hash map in which we can put in the list of words as values that are anagrams of each other.

3 But with the current logic, if the letter a appears 12 times and b 1 time (aaaa....b) - it would correspond to a key of 121. At the same time, even if the letter a appears 1 time and b 21 times (abbbbbbb....b) it would still correspond to the same key of 121. But clearly these two words are not anagrams. So in order to ensure that such cases are handled in terms of generating unique keys, we prepend a delimiter character like '#' while generating the key string from the frequency values of the array. That way the first case would correspond to #12#1 key and the second case would correspond to #1#21 key, thus resulting in two different keys for two words that are not anagrams of each other.

4 For each new word in the input list, refill the hash array with 0 in the beginning to compute a fresh set of frequency values for the word in contention. After delimiting and obtaining the key, if it is not contained in the hash map, add a list of String, to this new key, and add the word in contention as a value in the string list, to this key in the map.

5 At the end of iterating through all the words in the input list, return the list of Strings, by calling map.values() in order to return all the list of strings corresponding to each key, in a list of list of strings form.

Solution:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        
        //Sanity check
        if(strs == null || strs.length == 0)  return new ArrayList<>();
        
        //Declare a hashmap with String and list as k v
        HashMap<String, List<String>> map = new HashMap<>();
    
        //declare int array of 26 to hash each word into its character count
        int[] hash = new int[26];
        
        //iterate over each word in strs
        for (String word : strs) {
            
            //imp to fill count with 0 for each word
            Arrays.fill(hash, 0);
            
            //for each char in s converted to char Array increment corresp index relative to a
            for (char c : word.toCharArray()) hash[c - 'a']++;
            
            //Declare a sb
            StringBuilder sb = new StringBuilder();
            for(int i = 0 ; i < 26; i++) {
            //adding delimitter to ensure that a*12b*1 and a*1b*21 do not hash to same 121
            sb.append('#').append(hash[i]);
            }
            String key = sb.toString();
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<String>());
            }
            map.get(key).add(word);
        }
        
        return new ArrayList<List<String>>(map.values());
        
        //T O(n*m) n max length of one word in strs, and m length of strs
        //SO(n*m) n max length of one word in strs, and m length of strs
        
        
    }

//https://gist.github.com/harycane/737528316b231b3344e982dddcd7fb20

Complexity Analysis:

If n is the max length of any word in the input string array, and m is the length of input string array, then the time complexity is given by T O(n * m). Likewise, worst case space complexity would also be S O(n * m), with potentially m unique keys in the hash map each having a list of string as a value, of worst case size of any word in the string array, that of n.