49. Group Anagrams#

Difficulty: Medium

Link to Problem: To see the Group Anagrams problem on LeetCode, click here!

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.

Constraints:

  • 1 <= `strs.length <= \(10^4\)

  • 0 <= strs[i].length <= 100

  • strs[i] consists of lowercase English letters.

Solution:#

Here’s a Python function to solve this problem:

from collections import defaultdict


def groupAnagrams(strs):
    ans = defaultdict(list)

    # Iterate through the list of input strings
    for s in strs:
        # Initialize a list to represent character counts for each character (a-z)
        count = [0] * 26

        # Count the occurrences of each character in the current word
        for c in s:
            count[ord(c) - ord("a")] += 1

        # Use a tuple of character counts as the key and append the word to the anagram group
        ans[tuple(count)].append(s)

    # Convert the values (lists of anagrams) to a list of lists
    return list(ans.values())

Explanation:#

  1. Inside the method, a defaultdict called ans is created to store anagram groups. This dictionary will have a list as its default value, meaning that each key in the dictionary will be associated with an empty list by default.

  2. The code then iterates through the list of input strings, strs, using a for loop. For each word s in strs, it performs the following steps:

    • It initializes a list count of length 26, where each element represents the count of a specific character (a-z) in the word s.

    • The code then iterates through the characters of s. For each character c, it increments the corresponding count in the count list based on its ASCII value.

    • After counting the characters in s, it converts the count list into a tuple tuple(count) to use as a key for the ans dictionary.

    • It appends the word s to the list associated with the key (tuple) in the ans dictionary. This groups all anagrams of the same word together under the same key.

  3. After processing all words in strs, the code converts the values of the ans dictionary (which are lists of anagrams) to a list of lists using the list() constructor.

  4. Finally, the code returns the list of anagram groups, which is the result of grouping the anagrams in the input list.

In summary, the code efficiently groups anagrams together by counting the characters in each word and using a dictionary to store them under the same key. The result is a list of lists, where each inner list represents a group of anagrams.

Test cases#

# Example 1: Group anagrams from a list of words
strs1 = ["eat", "tea", "tan", "ate", "nat", "bat"]
result1 = groupAnagrams(strs1)
print(result1)

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

# Example 2: Group anagrams from a list with an empty string
strs2 = [""]
result2 = groupAnagrams(strs2)
print(result2)

[['']]

# Example 3: Group anagrams from a list with a single word
strs3 = ["a"]
result3 = groupAnagrams(strs3)
print(result3)

[['a']]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the groupAnagrams method:

Time Complexity:

  1. First, we create an instance of the Solution class, which is an O(1) operation.

  2. Inside the groupAnagrams method, we iterate through the list of input strings strs once in a loop:

    • For each word in strs, we perform character counting, which is done in O(K) time, where K is the maximum length of a word in the list.

  3. The overall time complexity of the method is O(N * K), where N is the number of words in the input list strs, and K is the maximum length of a word in strs.

Space Complexity:

  1. We use a defaultdict called ans to store the anagram groups. In the worst case, each word belongs to a distinct anagram group, so the space complexity for ans is O(N).

  2. Within the loop, we create a count list of length 26 to store character counts for each word. This is a fixed-size list and does not depend on the input size, so it has a constant space complexity of O(26), which is effectively O(1).

  3. The space used for other variables is also constant and does not depend on the input size.

  4. The final result, result, is a list of lists that contains the grouped anagrams. In the worst case, each word is a distinct anagram group, so the space complexity for result is O(N).

  5. The overall space complexity of the method is O(N) due to the space used by ans and result. The space used by the count list and other variables is constant and does not significantly affect the overall space complexity.

In summary, the time complexity of the groupAnagrams method is O(N * K), and the space complexity is O(N), where N is the number of words in the input list strs, and K is the maximum length of a word in strs.

Challenging Exercises:#

  1. Anagramic Palindromes: Given a list of strings, find all the groups of anagrams where each group contains words that can be rearranged into a palindrome. For example, in the list [“bat”, “tab”, “act”, “tac”, “dog”], there are two groups: [“bat”, “tab”, “act”, “tac”] and [“dog”].

  2. Largest Anagram Group: Given a list of strings, find the largest group of anagrams. Return the list of anagrams in that group. If there are multiple largest groups, return all of them.