# Find number of anagram groups ?

790 views

eg: array = "amber","gaura","sahil","mabre","rauag","halis", "bamre"}
then no. of anagram groups = 3.
"amber" ,"mabre" ,"bamre" form one group.

posted Nov 18, 2013

shall I assume all the char array have same length and same case? [lower / upper case]

+1 vote

OP1 : First sort each string lexicographically

if Given array is
array = {"amber","gaura","sahil","mabre","rauag","halis", "bamre"}
after above operation it will become
array = {"abemr","aagru","ahils","abemr","aagru","ahils", "abemr"}

OP2 : then sort the array
after above operation it will become
array = {"aagru","aagru","abemr","abemr","abemr","ahils","ahils"}

OP3 : Now the common strings are in sorted order so.. we can find number of groups easily in one single scan..

Order : Number of strings in array = n and length of each string is at max m then
OP1 : O(m)
OP2 : O(mnlogn)
OP3 : O(n)
Total : O(mnlogn)

Thanks Good one.
Can you please tell the complexity.
Similar Questions

Help me to write a C program which can generate list of numbers which are palindrome in decimal and octal notion. You can take some max as a limit find out all numbers which satisfy the given property between 1 to n.

A list contains a set of numbers, one number presents once and other numbers present even no. of times. Find out the number that occurs once in the list.

If we delete the mth number from a circle which is composed of numbers 0, 1, …, n-1 counting from 0 at every time, what is the last number?

For example, a circle is composed of five numbers 0, 1, 2, 3, 4. If we delete the 3rd number at every time, the deleted numbers are in order of 2, 0, 4, 1, so the last remaining number is 3.

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam