We are given N words. We have to divide the words into groups. Each word can go into a single group. In a group, any two words taken should be related.
Let us say we have two words. Let the set of unique alphabets in these words be A and B respectively. The words are related if the difference between sets A and B is at most one.
The difference of at most 1 means
- 1 unique character of A missing in B. Example A = ['a', 'b', 'c'] and B = ['a', 'b']
- 1 unique character of B missing in A. Example A = ['a', 'b'] and B = ['a', 'b', 'c']
- 1 unique character of A replaced by another unique character in B. Example A = ['a', 'b', 'c'] and B = ['a', 'b', 'd']
Find the minimum number of groups required to group all the words.
Constraints:
10 Testcases
1 <= N <= 10^4
1 <= len(word) <= 30
the words contain only lowercase alphabets
Sample Input:
4
aabcd
abc
efg
eert
Sample Output:
3
We need 3 groups [aabcd, abc],[efg],[eert]
A related question: What can be the maximum-sized group that we can form?
This can be solved using map and encryption, you have to encrypt the words into numbers( binary powers for each char that exists).
While travelling on the array just find whether its related char is present in the map before this operation, if not present increment the answer by 1. Push the current char before moving to the next character of the string.
final answer will be stored in answer (initialize it with 0 in the beginning).
Hope this question is not from the any ongoing contest
Can you please elaborate your approach with some example.
This question is not from any ongoing contest. It was asked in a hiring challenge a week back.
suppose the distinct characters are {a,b,c} so you can encrypt them as 2^0 + 2^1 + 2^2 = 7
other example can be {b,d} it can be encrypted as 2^1 + 2^3 = 10
Now the character from which they can make relation is either the charater absent from it , or an extra character (try to generate the encryption in the same way as described above) and check if any encryption exists before , it it exists is means this element will make a group with previous element.. So we need not to define a new group for it
Ok but in this way, which encryption is optimal to choose for the first word. It can have many. And if for a word any encryption is not found, which one to choose for this one.
A word having set as {a,b,c} can be in the group denoted by {a,b} also.
We are requested to find the number of groups , not the groups, so if a word is going to combine it will combine with any word , on the other hand if you see that we can generate all the possible encryptions for a word in constant time
For the first word , you don't need to check any group because it will not merge with any.
How are we going to check , that for current encrypted word we have a group already in which encrypted word have atmost one difference with current encrypted word?
you have to generate at most 26 words for the current word, that can be done for every word without exceeding the time limit.