• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Other related chapters:




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave