Longest String Chain

Moderate
0/80
profile
Contributed by
50 upvotes
Asked in companies
FacebookMathworksGroupon

Problem statement

You are given an array 'arr' of strings, where each string consists of English lowercase letters.


A string chain of 'arr' is defined as:

(1) A sequence of string formed using elements of 'arr'.

(2) Every string in the sequence can be formed by inserting a lowercase English letter into the previous string (except the first string).


Find the length of the longest possible string chain of 'arr'.


Example : 
Input: 'arr' = ["x", "xx", "y", "xyx"] 

Output: 3

Explanation:
The longest possible string chain is “x” -> “xx” -> “xyx”.
The length of the given chain is 3, hence the answer is 3.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'n' denoting the length of the 'arr'.

The next 'n' lines of the input contains elements of 'arr'.


Output Format : 
Return the length of the longest possible string chain with strings chosen from the given array.


Note : 
You don't need to print anything; it has already been taken care of. Just implement the function.


Sample Input 1 :
3
m 
nm 
mmm


Expected Answer :
2


Output on console :
2


Explanation For Sample Input 1 :
In this testcase, the longest possible string chain is "m" -> "nm".
The length of the given chain is 2, hence the answer is 2.


Sample Input 2 :
5
a 
bc 
ad 
adc 
bcd


Expected Answer :
3


Output on console :
3


Explanation For Sample Input 2 :
In this testcase, the longest possible string chain is “a” -> “ad” -> “adc”.
The length of the given chain is 3, hence the answer is 3.


Expected Time Complexity :
Try to solve this in O(n*n*l), where 'n' is the size of array 'arr' and 'l' is the maximum length of a string in 'arr'.


Constraints :
1 ≤ n ≤ 300    
1 ≤ arr[i].length ≤ 16

Time limit: 1 sec
Hint

Explore all the possibilities for each word.

Approaches (3)
Recursion

The total number of states are approximately equal to N ^ N. Note that state denotes a function call to ‘rec()’. In this approach, we generate all possible chains starting from ARR[I].

 

At the i’th position, we will explore the longest string chain which would be possible starting from this string(i’th). We will take the maximum of the length of all string chains possible from ‘i’ equal to 0 to ‘N’ - 1.

 

The recursion tree for ‘ARR’ = [“x”, “xx”, “y”, “xyx”] will be :

 

 

The steps are as follows :

  1. Sort the given array according to the string length in ascending order.
  2. Initialize a variable ‘ans’ to 0, this will store the length of the longest string chain.
  3. for ‘i’ in [0 . . N - 1]:
    • ‘ans’ = max(ans, rec(arr, i))
    • In rec() we go from the current string at index ‘i’ to all further strings for whom this current string at index ‘i’ can be a predecessor.
    • Initialize a variable ‘curr’ which will store length of longest string chain starting from ARR[i].
    • for ‘j’ in [i + 1 . . N - 1]:
  • if(predecessor(ARR[i], ARR[j]):
    • ‘curr’ = max(curr, 1 + rec(arr, j)).
  • Return ‘curr’.
Time Complexity

O( N ^ ( N + L ) ), where N is the length of the array and L is the max length of the string in the array.


 

For each of the strings in the array, we may have to explore all the remaining strings of the order ~N. The total number of states are approximately equal to N ^ N. Note that state denotes a function call to ‘rec()’. And every time we will also check for predecessor. 

Hence the time complexity is O( N ^ ( N + L ) ).

Space Complexity

O( N ^ 2 ), where N is the length of the array.


 

The maximum number of stack frames that could be present in memory at any point of time are ~N. And there will be N such recursive calls. Each function call take `O( N ) space and the maximum depth of the recursion tree is N.

Hence the space complexity is O( N ^ 2 ).

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