Longest String Chain | (DP- 45)

Prerequisite:

Problem Link: Longest String Chain

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.

Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this articleIf you want to suggest any improvement/correction in this article please mail us at [email protected]