# Longest String Chain | (DP- 45)

Prerequisite:

Problem Statement: We are given an array of strings (sat words[ ]), and we need to return the longest string chain. This longest string chain is defined as:

• A subsequence of words[ ] of the string.
• Every element of this subsequence ( a string) except the first one can be formed by inserting a single character into the previous element.
• The first element of this subsequence can be any string from the words[ ] array.

Example:

We need to print the length of the longest string chain, in this case: 4.

Two consecutive strings in this string chain need to have an insertion of a single character. The character can be added to any place on the string.

Solution:

This problem can be compared with the already discussed problem of /** link to dp-42 **/, the longest increasing subsequence.

There we used to compare two elements of the array and consider the previous element of the array if it was smaller than the current element.

In this problem, we will use the same technique and compare two values of the array and consider the previous element of the array, if it is just one character deletion from the current element.

Now, the main task is left to write this compare( ) function.

compare( S1, S2)

It returns true if the first string S1 is just a single character addition with S2 else it returns false. The way we have called the code, we expect S1 to be the larger string of the two. Therefore the length of S1 should be greater than the length of S2 by 1.

After checking for the length we can do a character matching using a two-pointer approach.

• We will declare two pointers first and second, initially set to the first index of S1 and S2 respectively.
• Then we set a while loop which will run till the first is less than the length of S1.
• In every iteration, if both the characters match, i.e S1[first] == S2[second], we increment both first and second by 1.
• Else, we will increment only first by 1.
• As S1’s length(say m) is just greater than S2’s length(say n) by 1 using the above pointer approach both the pointers should point to m and n simultaneously. If it happens we return true, else we return false.

For example:

Note: This question Longest String Chain expects us to find the longest chain subset instead of subsequence, therefore we will first sort the array (on the basis of the length of the string) to get the answer as discussed in /** link to dp-44 **/.

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

bool compare(string& s1, string& s2){
if(s1.size() != s2.size() + 1) return false;

int first = 0;
int second = 0;

while(first < s1.size()){
if(second < s2.size() && s1[first] == s2[second]){
first ++;
second ++;
}
else first ++;
}
if(first == s1.size() && second == s2.size()) return true;
else return false;
}

bool comp(string& s1, string& s2){
return s1.size() < s2.size();
}

int longestStrChain(vector<string>& arr){

int n = arr.size();

//sort the array

sort(arr.begin(), arr.end(),comp);

vector<int> dp(n,1);

int maxi = 1;

for(int i=0; i<=n-1; i++){

for(int prev_index = 0; prev_index <=i-1; prev_index ++){

if( compare(arr[i], arr[prev_index]) && 1 + dp[prev_index] > dp[i]){
dp[i] = 1 + dp[prev_index];
}
}

if(dp[i] > maxi)
maxi = dp[i];
}
return maxi;
}

int main() {

vector<string> words = {"a","b","ba","bca","bda","bdca"};

cout<<" The length of the longest string chain is : "<<longestStrChain(words);

}
``````

Output:

The length of the longest string chain is: 4

Time Complexity: O(N*N * l)

Reason: We are setting up two nested loops and the compare function can be estimated to l, where l is the length of the longest string in the words [ ] array. Also, we are sorting so the time complexity will be (N^2 * l + NlogN)

Space Complexity: O(N)

Reason: We are only using a single array of size n.

## Java Code

``````import java.util.*;

class LongestStrChain {
// Custom comparison function for sorting strings by length
static Comparator<String> comp = (s1, s2) -> s1.length() - s2.length();

// Function to compare two strings and check if they form a valid chain
static boolean compare(String s1, String s2) {
if (s1.length() != s2.length() + 1) {
return false;
}

int first = 0;
int second = 0;

while (first < s1.length()) {
if (second < s2.length() && s1.charAt(first) == s2.charAt(second)) {
first++;
second++;
} else {
first++;
}
}

return first == s1.length() && second == s2.length();
}

// Function to find the length of the longest string chain
static int longestStrChain(List<String> arr) {
int n = arr.size();

// Sort the array by string length
arr.sort(comp);

int[] dp = new int[n];
Arrays.fill(dp, 1);

int maxi = 1;

for (int i = 0; i < n; i++) {
for (int prevIndex = 0; prevIndex < i; prevIndex++) {
if (compare(arr.get(i), arr.get(prevIndex)) && 1 + dp[prevIndex] > dp[i]) {
dp[i] = 1 + dp[prevIndex];
}
}

if (dp[i] > maxi) {
maxi = dp[i];
}
}

return maxi;
}

public static void main(String[] args) {
List<String> words = Arrays.asList("a", "b", "ba", "bca", "bda", "bdca");

System.out.println("The length of the longest string chain is: " + longestStrChain(words));
}
}
``````

Output:

The length of the longest string chain is: 4

Time Complexity: O(N*N * l)

Reason: We are setting up two nested loops and the compare function can be estimated to l, where l is the length of the longest string in the words [ ] array. Also, we are sorting so the time complexity will be (N^2 * l + NlogN)

Space Complexity: O(N)

Reason: We are only using a single array of size n.

## Python Code

``````def is_predecessor(s1, s2):
# Check if s2 is a predecessor of s1
if len(s1) != len(s2) + 1:
return False

first = 0
second = 0

while first < len(s1):
if second < len(s2) and s1[first] == s2[second]:
first += 1
second += 1
else:
first += 1

return first == len(s1) and second == len(s2)

def longest_string_chain(arr):
n = len(arr)

# Sort the array in ascending order of string length
arr.sort(key=len)

dp = [1] * n
maxi = 1

for i in range(n):
for prev_index in range(i):
if is_predecessor(arr[i], arr[prev_index]) and 1 + dp[prev_index] > dp[i]:
dp[i] = 1 + dp[prev_index]

if dp[i] > maxi:
maxi = dp[i]

return maxi

if __name__ == "__main__":
words = ["a", "b", "ba", "bca", "bda", "bdca"]

result = longest_string_chain(words)

print("The length of the longest string chain is:", result)
``````

Output:

The length of the longest string chain is: 4

Time Complexity: O(N*N * l)

Reason: We are setting up two nested loops and the compare function can be estimated to l, where l is the length of the longest string in the words [ ] array. Also, we are sorting so the time complexity will be (N^2 * l + NlogN)

Space Complexity: O(N)

Reason: We are only using a single array of size n.

## JavaScript Code

``````function compare(s1, s2) {
if (s1.length !== s2.length + 1) return false;

let first = 0;
let second = 0;

while (first < s1.length) {
if (second < s2.length && s1[first] === s2[second]) {
first++;
second++;
} else {
first++;
}
}

return first === s1.length && second === s2.length;
}

function comp(s1, s2) {
return s1.length < s2.length;
}

function longestStrChain(arr) {
const n = arr.length;

// Sort the input array by string length in ascending order
arr.sort((s1, s2) => s1.length - s2.length);

// Initialize an array 'dp' with 1s
const dp = new Array(n).fill(1);

let maxi = 1;

for (let i = 0; i < n; i++) {
for (let prevIndex = 0; prevIndex < i; prevIndex++) {
if (compare(arr[i], arr[prevIndex]) && 1 + dp[prevIndex] > dp[i]) {
dp[i] = 1 + dp[prevIndex];
}
}

if (dp[i] > maxi) {
maxi = dp[i];
}
}

return maxi;
}

// Main function
function main() {
const words = ["a", "b", "ba", "bca", "bda", "bdca"];

const result = longestStrChain(words);
console.log("The length of the longest string chain is:", result);
}

// Call the main function
main();
``````

Output:

The length of the longest string chain is: 4

Time Complexity: O(N*N * l)

Reason: We are setting up two nested loops and the compare function can be estimated to l, where l is the length of the longest string in the words [ ] array. Also, we are sorting so the time complexity will be (N^2 * l + NlogN)

Space Complexity: O(N)

Reason: We are only using a single array of size n.