Home Strings [Leetcode] – Group Anagrams Solution

[Leetcode] – Group Anagrams Solution

by nikoo28
1 comment

Question: Given an array of strings strs, you need to group all the anagrams together. You can return the answer in any order.

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

Let us try to understand the problem statement and its test cases first.

You are provided with an array that has some strings. You need to group all the anagrams together. It could be possible that some strings don’t find anagrams, and that is perfectly fine. It can exist as an individual group. Return this group in any order.

Let us look at a sample test case:

image showing sample test case
Fig: Sample test case

You must also understand, what is an Anagram? Two strings are said to be anagrams of each other if they are made up of the same characters with same frequency. For example: the word LISTEN and SILENT are anagrams. They are composed of the letters E, I, L, N, S, T.

With this definition in mind, in the below image you can see all the highlighted anagrams. So, tan and nat are said to be anagrams and they form a group. Just like this, we need to group all the anagrams together, and form a resultant output.

Image showing grouped anagrams
Fig: Group Anagrams

A brute force method to solve this problem would be very obvious.

  • Iterate over each string in the input array.
  • For each string, check with each element of the array if they are anagrams.
  • If it is an anagram, add it to a group.
  • Else, move the string to a different group.

This method would work but you will run out of time trying to execute it for large test cases.

Method 1: Group by Sorting

One way to solve this problem is to group via sorting. Think about the properties of anagrams. If two words are anagrams of each other, they contain exactly the same characters. So, if we sort both of them, we should theoretically get the exact same string.

Let us look at a sample input.

Image showing sample input array
Fig: Sample input array

Now, as a next step, try to sort all of them and look at the sorted strings. You will find some strings that look exactly alike. That is because they were anagrams. You can now just compare these sorted strings.

Image showing all sorted strings
Fig: Sorting each string in the array

Once you have the sorted strings, you can create a hashmap, that will store all the groups. The key will be the sorted string, and the value would be the list of all the strings that are anagrams.

Image showing hashmap with grouped anagrams
Fig: Groups by sorting

After you iterate over all the strings, the values in the hashmap will give you the required groups. The time complexity of this approach depends on the sorting technique you use to sort the strings.

Implementation:

public List<List<String>> groupAnagramsCategorizeBySorting(String[] strs) { if (strs == null || strs.length == 0) return new ArrayList<>(); Map<String, List<String>> stringAnagramsMap = new HashMap<>(); for (String s : strs) { char[] arr = s.toCharArray(); Arrays.sort(arr); String key = String.valueOf(arr); if (!stringAnagramsMap.containsKey(key)) stringAnagramsMap.put(key, new ArrayList<>()); stringAnagramsMap.get(key).add(s); } List<List<String>> resultList = new ArrayList<>(); for (Map.Entry<String, List<String>> stringAnagrams : stringAnagramsMap.entrySet()) { resultList.add(stringAnagrams.getValue()); } return resultList; }
Code language: Java (java)

Time Complexity: O(n * \log k) (k is the length of largest string)
Space Complexity: O(n)

Method 2: Group by Frequency

It is however possible to improve the above approach a little bit. We can also take advantage of the fact that two anagrams have the same frequency of characters as well. So, instead of sorting the strings, we can also generate a new string to exhibit this property.

Example: The word KNEE and KEEN are anagrams. You can also say that both these words have K - 1 times, E - 2 times and N - 1 time. Using this method we can create some kind of a frequency string which can be something like E2K1N1. Notice that this string would be same for both the words.

Let us take up an example once again.

Image showing sample input array
Fig: Input array

We can now create frequency strings for each of these strings. They will look like:

aab = a2b1 aba = a2b1 baa = a2b1 abbccc = a1b2c3 abb = a1b2 bcbcca = a1b2c3
image showing generated frequency strings
Fig: Creating frequency strings

Looking closely at the frequency strings, you can conclude that all anagrams will generate the same frequency strings. This gives you some key to group all the anagrams. Once again, you can create a hashmap that will have the key as the frequency string, and the value would be a list of all the anagrams

image showing grouped anagrams by frequency string
Fig: Grouping by frequency

After you iterate over all the strings, you should have all your groups in the values of the hashmap. The time complexity of this approach can be better as frequency strings can be generated in linear time.

Implementation:

public List<List<String>> groupAnagramsCategorizeByFrequency(String[] strs) { // Check for empty inputs if (strs == null || strs.length == 0) return new ArrayList<>(); Map<String, List<String>> frequencyStringsMap = new HashMap<>(); for (String str : strs) { String frequencyString = getFrequencyString(str); // If the frequency string is present, add the string to the list if (frequencyStringsMap.containsKey(frequencyString)) { frequencyStringsMap.get(frequencyString).add(str); } else { // else create a new list List<String> strList = new ArrayList<>(); strList.add(str); frequencyStringsMap.put(frequencyString, strList); } } return new ArrayList<>(frequencyStringsMap.values()); } private String getFrequencyString(String str) { // Frequency buckets int[] freq = new int[26]; // Iterate over each character for (char c : str.toCharArray()) { freq++; } // Start creating the frequency string StringBuilder frequencyString = new StringBuilder(""); char c = 'a'; for (int i : freq) { frequencyString.append(c); frequencyString.append(i); c++; } return frequencyString.toString(); }
Code language: Java (java)

Time Complexity: O(n * k) (k is the length of the largest string)
Space Complexity: O(n)

As always, the complete code and its test cases can be found on Github as well.

Video Explanation:

You may also like

1 comment

Rahul Jain October 9, 2021 - 04:15

Hi Geeks
You can checkout an easy explanation for the problem in the below video :)

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More