Help needed in String problem.

Правка en1, от ChitreshApte, 2021-06-21 09:26:05

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?

Теги strings, graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ChitreshApte 2021-06-21 09:26:05 1115 Initial revision (published)