Longest String Chain

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

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.

You can see in the recursion tree of approach 1 that there are many overlapping subproblems. We can use memoization here.

The steps are as follows :

1. Sort the given array according to the string length in ascending order.
2. Initialize all values of array ‘DP’ to -1. This means the value is not yet calculated.
3. Initialize a variable ‘ans’ to 0, this will store the length of the longest string chain.
4. for each ‘string’ in ’ARR’:
   • If the value of this ‘string’ is -1 then only proceed.
   • Initialize a variable ‘curr’ to 1, this will store the length of the longest string chain ending at ‘string’.
   • We go further till the end of the array and check if the current ‘string’ is the predecessor of the next string. If so, then we update ‘curr’.
   • We can check if ‘a’ is the predecessor of ‘b’ simply by checking if ‘a’ is the subsequence of ‘b’ and the difference between lengths of ‘b’ and ‘a’ is 1.
   • In the recursive call at starting we check if the value of that string is already computed or not, if computed then we directly return that value.
   • Also at the end of each call, we update the value of the word in the ‘DP’ array.

First, we sort ‘ARR’ according to the length of strings. 

We start from the first string and iterate through all the characters of this string and check by removing any character if the string already exists in the map. If it exists then we take a maximum of all such cases. In the map, we store the string and length of the longest string chain ending at that string.

Let’s take ‘ARR’ = [“x”, “xx”, “y”, “xyx”]

Initialize ‘maxChain’ to 0.

Our first string is “x”. Initialize ‘curr’ for “x” to 1. We go through all characters and see by removing one by one. Here only 1 character is there so we will directly insert it into the map along with ‘curr’. Now ‘maxChain’ becomes 1.

Now our string is “xx”. Initialize ‘curr’ for “x” to 1. Now we see that by removing the first “x” we find that “x”(after removing) is already in the map, so we update ‘curr’ as max(curr, 1 + mp[“x”]). Hence ‘curr’ becomes 2. And we insert “xx” and 2 in the map. Now ‘maxChain’ becomes 2.

Now our string is “y”. Initialize ‘curr’ for “y” to 1. We go through all characters and see by removing one by one. Here only 1 character is there so we will directly insert it into the map along with ‘curr’. Now ‘maxChain’ remains 2.

Now our string is “xyx”. Initialize ‘curr’ for “xyx” to 1. Now we see that by removing “y” we find that “xx” is already in map, so we update ‘curr’ as max(curr, 1 + mp[“x”]).

Hence ‘curr’ becomes 3. And we insert “xyx” and 3 in the map. Now ‘maxChain’ becomes 3.

Hence our longest string chain is of length 3 and is [“x”, “xx”, “xyx”].

The steps are as follows :

1. Create an unordered map of <string, int> for storing string and length of longest string chain ending at that string.
2. Sort the array of strings according to their lengths in ascending order.
3. Declare ‘maxChain’ as 0.
4. for ‘str’ in ‘ARR’:
   • Declare ‘chainLength’ as 1.
   • for i in [0 . . str.length - 1]:
     • Create string s = str[0 : i] + str[i + 1 : ]
     • If s exists in map, then update ‘chainLength’.
   • Insert the given word with its ‘chainLength’ in map.
   • Update ‘maxChain’.