DAY 25 - Longest String Chain
Tags: learning, css, leetcode, cpp
Published: 2023-06-28 19:30:03

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