Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Approach1:

We know that two string are anagrams if their sorted strings are equal.

• Iterate through the Strings of array

• We sort each String that we encounter in the loop and use it as Key

• Since the Keys consist of sorted Strings therefore all anagrams will share the same key.

• Essentially, when collision occurs (When two strings are anagram), we add that String to that it's respective place in the map.

• Finally, we return the values of the HahsMap as it contained all the anagrams grouped in groups.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for(String s : strs){
            char[]a = s.toCharArray();
            Arrays.sort(a);
            String key = String.valueOf(a);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

Time: O(mklogk) Space: O(mk)

Approach2: Optimal

After completing our first-approach, we notice that we might be able to optimize our algorithm. Primarily due to the fact that we know that our Strings will only contain lower-case english letters. This subsequenly allows us to use Counting Sort which is an O(N) sorting algorithm in lieu of Arrays.sort() which is a nlogn algorithm (quickSort).

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for(String s : strs){
            int[]freq = new int[26];
            for(int i = 0; i < s.length(); i++)
                freq[s.charAt(i) - 'a']++;
            String key = Arrays.toString(freq);
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

Time: O(mk) Space: O(mk)

Approach3: Brute-force

When first presented with this problem, the below implementation is also an intuitive approach however the time complexity is exponential.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Set<List<String>> set = new HashSet<>();
        List<String> list = new ArrayList<>();
        
        for(int i = 0; i < strs.length; i++){
            char[]ch = strs[i].toCharArray();
            Arrays.sort(ch);
            for(int j = 0; j < strs.length; j++){
                char[]a = strs[j].toCharArray();
                Arrays.sort(a);
                if(Arrays.equals(ch, a)){
                    list.add(strs[j]);
                }
            }
            set.add(new ArrayList<>(list));
            list.clear();
        }
        return new ArrayList<>(set);
    }
}

Time: O(mklogk2) Space: O(mk)