Programming Interview Question — Longest String Chain

Lintcode 257 or Leetcode 1048

Question setup

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

Input: ["ba","a","b","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Visualizing with the Example

Let’s attempt to find the maximum chain length for each word. To help, we first re-arrange the words by their length i.e. shortest length to longest length. Also, we will also show the word string if one character is deleted right beside it.

You can then trace the chain length. In the example above, for word ‘bca’, we can find ‘ba’ and from ‘ba’ traced back to ‘b’. Hence the string chain is length 3. And if we trace exhaustively, we can see that the maximum string chain is length 4, as marked in the diagram above.

You can also find other chains as shown below. Some chains lead to dead-end, since the predecessor word such as ‘ca’ is not even in the word list.

Data structure and Algorithm

We need a way to automate the tracing of the chain. That’s where we can consider to use the dictionary data structure. Let’s define dpDict dictionary, where the key is the word and the value of the dictionary is the longest chain length with the word at the end of the chain.

Again we start from the shortest word and traverse to the longest word in the word list. For each of the word, we go through the different permutation whereby one character is deleted. We try to find the permutation in the dpDict. If it’s not in the dictionary, we return value length 0, else return whatever is the length of the chain with the permutation at the end of the chain. Then for the word, store in the dictionary the longest length of the chain of a permutation and plus 1 i.e. +1. The “+1” is since the word will now be at the end of the chain, so we must count it’s (the words) own length.

Python Code

Well, hope the explanation is useful to your understanding. In the meantime, happy coding!