Teaching Kids Programming – Largest Anagram Group

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of strings words, group all anagrams together and return the size of the largest grouping.

Constraints
n ≤ 5,000 where n is length of words.
Example 1
Input
words = [“ab”, “ba”, “abc”, “cba”, “bca”, “ddddd”]
Output
3
Explanation
[“abc”, “cba”, “bca”] is the largest grouping

Algorithm to Compute Largest Anagram Group via Hash Table

We use a dictionary to store the occurence for each anagram. All the strings when sorted are the same if they belong to the same anagram group.

Anagrams are strings that have same set of characters but in different orders, for example, “abc” and “cba” are anagrams.

1
2
3
4
5
6

class Solution:
    def largestAnagramGroup(self, words):
        a = defaultdict(int)
        for w in words:
            a[''.join(sorted(w))] += 1
        return max(a.values())

class Solution:
    def largestAnagramGroup(self, words):
        a = defaultdict(int)
        for w in words:
            a[''.join(sorted(w))] += 1
        return max(a.values())

Then, we compute the max values in the dictionary – which is the size of the largest anagram group.

We can also use one-liner – and use the Counter to record the occurrences

1
2
3

class Solution:
    def solve(self, words):
        return max(Counter(tuple(sorted(word)) for word in words).values())

class Solution:
    def solve(self, words):
        return max(Counter(tuple(sorted(word)) for word in words).values())

The time complexity is O(NMLogM) and the space complexity is O(N) where N is the number of the strings, and M is the length of each string in the list.

–EOF (The Ultimate Computing & Technology Blog) —