Program to find the largest grouping of anagrams from a word list in Python

Question

Program to find the largest grouping of anagrams from a word list in Python

PythonServer Side ProgrammingProgramming

---

---

Suppose we have a list of strings words, we have to group all anagrams together and return the size of the largest grouping.

So, if the input is like words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"], then the output will be 3, as ["xyz", "zyx", "yzx"] is the largest grouping.

To solve this, we will follow these steps −

• lookup := a new map, initially empty

• res := 0

• for each i in words, do

  • p := sort i in lexicographical way

  • if p is in lookup, increase count, otherwise 1

  • res := maximum of res and lookup[p]

• return res

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:
   def solve(self, words):
      lookup = {}
      res = 0
      for i in words:
         p = "".join(sorted(i))
         lookup[p] = lookup.get(p, 0) + 1
         res = max(res, lookup[p])
      return res
ob = Solution()
words = ["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]
print(ob.solve(words))

Input

["xy", "yx", "xyz", "zyx", "yzx", "wwwww"]

Output

3

Arnab Chakraborty

Published on 09-Oct-2020 18:22:06

Previous Page Print Page

Next Page  

Advertisements