DAY 25 - Longest String Chain

Hey Guys! Nayan here and this is the 25th day of the 100-DAY challenge. If you are reading this for the first time , I learn and solve some questions throughout the day and post them here.

Let's get right to the problem.

DAY 25 Problem: Longest String Chain

You are given an array of words where each word consists of lowercase English letters.

word1 is a predecessor of word2 if and only if we can insert exactly one letter anywhere in word1 without changing the order of the other characters to make it equal to word2.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".
A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Intuition and Observation:

Let's first identify what the question wants from us in simpler terms and then start our approach towards the solution.

To put it in a reverse way, the questions wants us to check that if the next possible string is possible to convert to previous with a single deletion or is it a subsequnce of it of size-1.

For example:
a,ba,bda,bdca: It is possible to form bda from bdca but elimination of one character.

So we don't need to generate all subsets rather we can start from the index of our given vector and check only those which are possible.

We are going to use somewhat of longest increasing subsequence problem here.

Let's write down the approach:

• We need two comparators here. One is to sort the array in order of increasing size, so that we can form our subsequence.
• We need a boolean function here to return true or false if it's possible to make a chain from the next element.
• It has two conditions: If the size is greater than size+1 of the previous index it automatically loses out as it has more than one characters.
• Second if it has same size, we shall do character matching and check if the order is okay.
• Third we will follow the same code as longest increasing subsequence to find out the longest string chain.

NOTE Incase I have not solved longest Increasing subsequence yet, Please forgive me, I have probably forgotten to upload it. I will upload it ASAP.

Code:

static bool comp(string &s1, string &s2){
        return s1.size() < s2.size();
    }
    bool checkPossible(string &s1, string &s2){
        if(s1.size() != s2.size()+1) return false;
        int i = 0;
        int j = 0;
        while(i < s1.size()){
            if(s1[i] == s2[j]){
                i++;
                j++;
            }
            else{
                i++;
            }
        }
        if(i == s1.size() && j == s2.size()){
            return true;
        }
    return false;    
    }
    int longestStrChain(vector<string>& words) {
        int n = words.size();
        //tabulation
        sort(words.begin(),words.end(),comp);
        int maxi = INT_MIN;
        vector<int> dp(n, 1);
        for(int i = 0 ; i < n; i++){
            for(int prev = 0; prev < i; prev++){
                if(checkPossible(words[i], words[prev])){
                    dp[i] = max(dp[prev]+1, dp[i]);
                }
            }
            maxi = max(dp[i],maxi);
        }
        return maxi;
    }

Complexity Analysis:
Time: O(N^2*L + nLogn)
Space: O(N). where L is the length of string checking.

Thanks for reading. I will try to upload a better solution by tomorrow.