ChitreshApte's blog

By ChitreshApte, history, 5 weeks ago, In English

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?

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like 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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              you have to generate at most 26 words for the current word, that can be done for every word without exceeding the time limit.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I got the same question in my coding round, Though i came up with n^2 approach and only partial got accepted , (for that i made a graph with all realted strings and counted number of components in that graph)