Group Anagrams

Problem Description

We have given a string list and asked to group the anagrams together. Only lowercase english letters are used.
For full explanation: Group Anagrams

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

Intuition

Let's define anagram first. An anagram is a word or phrase created by rearranging the letters of another word or phrase, using each letter exactly once.
Here is an example of anagram words: ate, eat, tea

There is actually an easy problem called Valid Anagram simply asks if two strings are anagram to each other or not, let's solve them gradually.

Starting with Valid Anagram, one of the brute force solutions comes to my mind while i'm writing these lines is:

• Check the length, if equals continue
• Sort two strings by character
• Check if they are equal or not

public boolean isAnagram(String s, String t) {
  if(s.length() != t.length()) return false;
  char[] sc = s.toCharArray();
  char[] tc = t.toCharArray();
  Arrays.sort(sc);
  Arrays.sort(tc);
  return String.valueOf(sc).equals(String.valueOf(tc));
}

Due to sort operations, this gives us O(nlogn) complexity, can we make it better?

Please note that problem gives us condition/hint that only lowercase english letters are allowed for the test cases. If we know all the possible characters, maybe we can develop a better approach.

We can create a space for limited characters and use it for both string's characters. Here's how so:

• Check the length, if equals continue
• Create an integer array with size of 26
• Loop through string-s and increment corresponding slot by 1
• Loop through string-t and decrement corresponding slot by 1
• At the end of it, if the array contains all zeros, then we have an anagram

public boolean isAnagram(String s, String t){
  if(s.length() != t.length()) return false;
  int[] map = new int[26];
  for (Character c : s.toCharArray()) map[c-'a']++;
  for (Character c : t.toCharArray()) map[c-'a']--;
  for (Integer i : map){
    if(i!=0) return false;
  }
  return true;
}

Regardless from how characters are sorted, same character goes to same slot by it's ASCII value. The reason of c-'a' is start the english lower case letter from zero and meet them at the end of the 26th slot.

We can reduce one loop by moving the condition to the second loop because we already checked the length of the strings at the beginning

public boolean isAnagram(String s, String t){
  if(s.length() != t.length()) return false;
  int[] map = new int[26];
  for(Character c : s.toCharArray()) map[c - 'a']++;
  for(Character c : t.toCharArray()) {
    if(map[c -'a'] == 0) return false;
    map[c - 'a']--;
  }
  return true;
}

Continuing with Group Anagrams, there should be an indicator/key that tells us which string goes to which group (sorting or better) and also we need to keep track of every string with it's group, i want you to think on that.

public List<List<String>> groupAnagrams(List<String> strs){
  if(strs == null || strs.length == 0) return new ArrayList<>();
  Map<String,List<String>> map = new HashMap<>();
  for(String str : strs){
    char[] ch = str.toCharArray();
    Arrays.sort(ch);
    String key = String.valueOf(ch);
    if(!map.containsKey(key)) map.put(key,new ArrayList<>());
    map.get(key).add(str);
  }
  return new ArrayList<>(map.values());
}

We have a loop and sorting operation inside of a loop so complexity is O(n*nlogn) but do we really need sorting? We need an indicator/key regardless of what it is and how it's generated, the key is not included to the result.

Here is a better approach with O(n2) result;

public List<List<String>> groupAnagrams(List<String> strs){
  if(strs == null || strs.length == 0) return new ArrayList<>();
  Map<String,List<String>> map = new HashMap<>();
  for(String str : strs){
    char[] ch = new char[26];
    for(Character c : str.toCharArray()) ch[c-'a']++;
    String key = String.valueOf(ch);
    if(!map.containsKey(key)) map.put(key,new ArrayList<>());
    map.get(key).add(str);
  }
  return new ArrayList<>(map.values());
}