Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 14 Jan, 2022

Longest String Chain

Moderate
Asked in companies
FacebookGoogleMathworks

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.


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.


Approaches

01 Approach

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’.