Longest String Chain
Given a list of words, find the length of the longest chain of words where each word is formed by adding exactly one letter, at any position, to the word before it.
Word A is a predecessor of word B if B can be formed by inserting exactly one letter into A. A chain word1 -> word2 -> ... -> wordN is valid when every word is a predecessor of the next one. A single word on its own counts as a chain of length 1.
Input & Output
Input
words — the list of words to build the chain from
Output
the length of the longest chain that can be formed from the words
Example
Input
words = ["a", "b", "ba", "bca", "bda", "bdca"]
Output
4
Explanation
The chain "a" -> "ba" -> "bda" -> "bdca" has length 4. Each step inserts one letter: b at the front, then d in the middle, then c. No longer chain exists.
Example
Input
words = ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]
Output
5
Explanation
Every word belongs to one chain: "xb" -> "xbc" -> "cxbc" -> "pcxbc" -> "pcxbcf". The words are not given in chain order, so the order they appear in the list carries no information.
Constraints
1 <= words.length <= 10001 <= words[i].length <= 16words[i]consists of lowercase English letters