You are given a list of N words (strings containing only lower case letters of the English alphabet).
We consider two words to be equivalent if they contain the same letters, i.e. we can rearrange the letters of one word in order to obtain the other word.
Compute the size of the largest subset of equivalent words.You should assume the input is quite large (there are about 10^5 letters in total).
Input
The first line contains a single integer value
Each of the following N lines contains a single string, representing one of the words.
Output
The output should contain a single integer representing the size of the largest subset of equivalent words.
Sample Input
6
cats
caller
dogs
cellar
parrots
recall
Sample Output
3
Explanation
caller, cellar and recall are (the only) equivalent words.
What I have tried:
import java.util.Scanner;
import java.io.*;
import java.util.Arrays;
class Main
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String list[]=new String[n];
for(int i=0;i<n;i++)
{
list[i]=sc.next();
}
int ans=0;
for(int i=0;i<n;i++)
{
int count=0;
for(int i2=i+1;i2<n;i2++)
{
if(isAnagram(list[i],list[i2]))
count++;
}
if(count>ans)
ans=count;
}
System.out.println(ans+1);
}
public static boolean isAnagram(String s1, String s2){
if (s1.length() != s2.length()) return false;
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
for(int i = 0; i < c1.length; i++) {
if(c1[i] != c2[i]) return false;
}
return true;
}
}
Submit an article or tip