   Find number of anagram groups ?

773 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) answer Nov 24, 2013 by
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.