Medium · Dynamic Programming

Longest String Chain

Given an array of words, return the length of the longest word chain, in which each word is the previous word with exactly one letter inserted anywhere, the other letters keeping their order. A single word is a chain of length 1.

Examples

Example 1

["a","b","ba","bca","bda","bdca"]

Output: chain = 4

Example 2

["xbc","pcxbcf","xb","cxbc","pcxbc"]

Output: chain = 5

Rebuild it in the studio

Core interview problems are free with a full runner and lessons; Pro opens the complete library.

More Dynamic Programming problems