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
A related question: What can be the maximum-sized group that we can form?