Longest Word

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in companies
UberAppleAmazon

Problem statement

You are given an array/list of words ‘ARR’. Your task is to find all the words having the longest length which can be made from some other words on the list.

Note :

Return the list of all those words sorted in alphabetical. Return an empty list in case there are no such words

For Example :

Input: cat, banana, dog, nana, my, walk, walker, baby, dogwalkers, s, babymybaby

Output: babymybaby dogwalkers

Here in the given list of words, you can see that the words babymybaby, dogwalkers contain the words present in the list i.e. ‘s’, 'dog’, ‘walker’,‘baby’ and ‘my’ and both are of the same length.
Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains the integer 'N', denoting the number of words that you will be given. Then N lines follow.

Each of the next 'N' lines contains a word denoting the elements of the word ARR.

Output format :

For the given list of ‘N’ words, print all such words in lexicographical order.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= N <= 1000
1 <= length of longest word <= 100

Where ‘N’ is the given list of words.

Time limit: 1 second

Sample Input 1 :

5
test
tester
testertest
testing
testingtester

Sample Output 1 :

testingtester

Explanation Of Sample Input 1 :

Here in the given list of words, you can see that the word ‘testingtester’ contains both the words present in the list i.e. testing and tester.

Sample Input 2 :

11
cat
banana
dog
nana
my
walk
walker
baby
dogwalkers
s
babymybaby

Sample Output 2 :

babymybaby dogwalkers
Hint

Can we recursively search for finding the longest word which would be comprised of words from the list to solve this problem?

Approaches (1)
Recursion

The key observation here is to notice a simple fact that the longest word would be the one whose substring splits in all possible ways are also present in the list.

The algorithm for the same can be as follows:- 

 

Steps:

  • Sort the elements (words) given in the list in descending order of their lengths (arrange them lengthwise)
  • Store the sorted elements in the list in a Set (having only unique strings)
  • Now start with the first string and loop over sorted strings.
  • While Iterating in the list of words recursively, check whether the words when divided into different possible substrings are also present in the set where all unique strings are stored.
    1. Return True from the recursive check if some part of the substring from the word is present in the set and recursively continue checking the same for the remaining part. Call the recursive function on the remaining part of the substring to make sure that the word is comprised of all substrings present in the list as well.
    2. Otherwise, if there are substrings in the word which are not present in the list then, return False.
  • We finally add the longest such words obtained from the list and add them to another list.
  • Return the final list of words sorted in alphabetical order.
Time Complexity

O(N * L * L), where ‘N’ is the number of words present in that list (array) and ‘L’ is the length of the longest word.

 

Now, since there are N iterations in total each for L splits in each possible ways. And for each possible substring match in the list we call recursively for the remaining (L-1) length of the word. So the time complexity grows by O(N * L * L).

Space Complexity

O(N), where ‘N’ is the number of words present in that list (array).

 

Since a set of upto ‘N’ words is being used for looking up elements present in the given list. So the space used here is O(N).

Code Solution
(100% EXP penalty)
Longest Word
Full screen
Console