49. Group Anagrams

Hello, reader 👋🏽 ! Welcome to day 28 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 49. Group Anagrams.

🤔 Problem Statement

Given a list of strings, group the anagrams together and return the list of groups in any order.
E.g.:
- strs = ["eat","tea","tan","ate","nat","bat"] => [["bat"],["nat","tan"],["ate","eat","tea"]]
- strs = ["ddddddddddg","dgggggggggg"] => [["dgggggggggg"],["ddddddddddg"]]

💬 Thought Process - Sorting I

Since anagrams are strings with the same frequency of characters that are rearranged, if we sort each strings, all the anagrams will have the same result after sorting.
E.g.: In the following list: ["eat","tea","tan","ate","nat","bat"], when we sort all of them, eat, tea, and ate will have the same sorted result => aet
To group anagrams, we can use a hash table that maps the sorted strings to the original strings.

Something like this:

"aet" => ["eat", "tea", "ate"]
"ant" => ["tan", "nat"]
"abt" => ["bat"]

Now let's move on to the code for this.

👩🏽‍💻 Solution - Sorting I

Below is the code for the approach where we sort all n strings.

class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
      Map<String, List<String>> map = new HashMap();

      for(String str: strs) {
          String sortedStr = getSortedString(str); 
          if(!map.containsKey(sortedStr)) {
              map.put(sortedStr, new ArrayList());
          }

          map.get(sortedStr).add(str);
      }

      List<List<String>> list = new ArrayList();
      for(String key: map.keySet()) {
          list.add(map.get(key));
      }

      return list;
  }

  private String getSortedString(String s) {
      char[] sArr = s.toCharArray();
      Arrays.sort(sArr);

      return new String(sArr);
  }
}

Time Complexity: O(n * m*log m)
  - n = number of strings
  - m = average length of strings
      - Since we are sorting all the strings, it will take O(m*log m), and this is done for n strings. 
Space Complexity: O(n) 
  - n = number of strings
      - We are using a map of list to store n strings.

💬 Thought Process - Sorting II

In the above approach we sorted each of the strings which takes m*logm. We can avoid this by using the fact that the strings only contain lowercase alphabets.
We can use a count array of size 26 that keeps track of the frequencies of every letter in a string.
Then we can iterate from 0 to 25 and build the string in the sorted order from a to z.
For e.g.: string eat will have the following count array representation:
- [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
Now, we can build string from 0th index to the 25th index by appending character at index i, count[i] times.
So, if we had something like this:
- [5, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- It would represent aaaaab
From the count array for eat we will build: aet.
We can do this for all n strings. Building the count array takes O(m) as well as building a string from that array. This way we can bring down O(m*logm) to O(m).
With this idea, let's look into the code.

👩🏽‍💻 Solution - Sorting II

Below is the code for building sorted strings from a frequency array.

class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
      if(strs == null || strs.length == 0) {
          return new ArrayList();
      }

      List<List<String>> groups = new ArrayList();
      Map<String, List<String>> map = new HashMap();

      for(String str: strs) {
          String sortedStr = getSortedString(str);
          if(!map.containsKey(sortedStr)) {
              map.put(sortedStr, new ArrayList());
          }
          map.get(sortedStr).add(str);
      }

      for(String sortedStr: map.keySet()) {
          System.out.println(sortedStr);
          groups.add(map.get(sortedStr));
      }

      return groups;
  }

  private String getSortedString(String s) {
      int[] count = new int[26];

      for(int i = 0; i<s.length(); i++) {
          char ch = s.charAt(i);
          count[ch - 'a']++;
      }

      StringBuilder sb = new StringBuilder();
      for(int i = 0; i<26; i++) {
          int c = count[i];
          char ch = (char)('a' + i);
          while(c-- > 0) {
              sb.append(ch);
          }
      }

      return sb.toString();
  }
}

Time Complexity: O(n * m)
  - n = number of strings
  - m = average length of strings
Space Complexity: O(n) 
  - n = number of strings
      - We are using a map of list to store n strings.

Another tiny improvement (although not better in terms of time) is to stop at building the count array. We can simply use the string representation of this array as a key.
For e.g.: the count array representation for eat, tea and ate will all be:
- [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
- And the string representation would just be:
  - "[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]"
So, we could directly use this representation rather than building another string out of it!

Note: At least this is possible in Java. Not sure about other languages!

👩🏽‍💻 Solution - String Representation of Count Array as Map Keys

Below is the teensy tiny improvement for directly using the count array as a string.

class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
      if(strs == null || strs.length == 0) {
          return new ArrayList();
      }

      List<List<String>> groups = new ArrayList();
      Map<String, List<String>> map = new HashMap();

      for(String str: strs) {
          String countRepresentation = getCountRepresentation(str);
          if(!map.containsKey(countRepresentation)) {
              map.put(countRepresentation, new ArrayList());
          }
          map.get(countRepresentation).add(str);
      }

      for(String countRepresentation: map.keySet()) {
          groups.add(map.get(countRepresentation));
      }

      return groups;
  }

  private String getCountRepresentation(String s) {
      int[] count = new int[26];

      for(int i = 0; i<s.length(); i++) {
          char ch = s.charAt(i);
          count[ch - 'a']++;
      }

      // The array's string representation
      return Arrays.toString(count);
  }
}

Time Complexity: O(n * m)
  - n = number of strings
  - m = average length of strings
Space Complexity: O(n) 
  - n = number of strings
      - We are using a map of list to store n strings.

From LeetCode, you can find other solutions as well. Like this crazy smart solution that used prime numbers to represent alphabets characters. The summation of the frequency and the prime representation for all the characters were used as a map.
You can find the code for this question in the GitHub repo here: 49. Group Anagrams.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!