Group Anagrams

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given an array of words, group all anagrams together and return a list of lists

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Sorting an anagram and using that as a key for Hash Map would lead to $O(nlogn\ast wordLength)$
• We need to solve the problem in $O(n\ast wordlength)$
• Input is lower-case letters only

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Key of anagram is made by converting the letter to count dictionary to a string
• Looping over 26 characters in the alphabet and getting count of that letter from dictionary is $O(1)$

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Hash Map

Time & Space Complexity

• Time: O($n\ast wordlength$) → Reason:
• Space: O($ $) → Reason:

Code

class Solution:
    """
    Time: O(nc)
    Space: O(n)
    """
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = {}
        for word in strs: # O(n)
            count = self.countLetters(word) # O(c) - average length of word
            key = self.convertDictToKey(count) # O(1)
            result[key] = result.get(key, [])
            result[key].append(word)

        return list(result.values()) # O(n)

    """
    Time: O(n)
    Space: O(n) 
    """
    def countLetters(self, word):
        countOfLetters = {}
        for letter in word:
            countOfLetters[letter] = countOfLetters.get(letter, 0) + 1
        return countOfLetters

    """
    Time: O(1)
    Space: O(1)
    """
    def convertDictToKey(self, countOfLetters):
        start = ord("a")
        end = ord("z")
        result = []
        for l in range(start, end + 1):
            letter = chr(l)
            if letter in countOfLetters:
                result.append(f"{letter}:{countOfLetters[letter]}")
        return "".join(result)

Alternative Solution

def groupAnagrams(strs):
    """
    Time Complexity: O(N * K) where N = number of strings, K = max length of string
    Space Complexity: O(N * K) for storing the result
    """
    from collections import defaultdict
    
    anagram_groups = defaultdict(list)
    
    for s in strs:
        # Count frequency of each character
        char_count = [0] * 26
        for char in s:
            char_count[ord(char) - ord('a')] += 1
        
        # Use tuple of counts as key (lists aren't hashable)
        key = tuple(char_count)
        anagram_groups[key].append(s)
    
    return list(anagram_groups.values())

Common Mistakes / Things I Got Stuck On

• How to get all the values of a dictionary in a list

list(dictionary.values()) # value order not guaranteed

• How to convert ascii to letter chr() and vice versa ord()