🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Given a list of words, each word consists of English lowercase letters.
Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".
A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.
Return the longest possible length of a word chain with words chosen from the given list of words.

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

Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]

Output: 5

Solution:

This is a wonderful problem and one of my recent favorites. This is a problem where you can use both Longest Increasing Subsequence and Longest Common Subsequence. This, to me, makes this a beautiful problem.

This problem has the following characteristics :

• We are interested in finding largest subset of the given list or array maintaining the given condition of predecessor relation.

So this problem fits the pattern of problems easily solvable by Longest Increasing Subsequence.
In fact we see that once we sort the given string array based string length, this problem translates to finding longest increasing subsequence based on given predecessor condition.

Next big challenge is to figure out a sleek way of determining if a string a is predecessor of string b (length of string b > length of string a). Notice that except one character in string b, all other characters in string b would be present in string a and they would be in same order as that in string b. So basically if we compute Longest Common Subsequence of string a and string b will be equal to the length of string a.

Let's now look at the code below:

Java code:



Login to Access Content




Python Code:



Login to Access Content

Other related chapters:

• Core Concept
• Box Stacking
• Russian Doll Envelopes
• Largest Divisible Subset
• Best Team with No Conflict
• Longest Bitonic Subsequence

Instructor: