Editor

Longest Word Chain

#637 · Dynamic programming · Advanced · Fast enough · 150 XP · about 30 min

In a word chain each word is made from the one before it by inserting exactly one letter, at the front, at the end or anywhere in between, without moving the other letters. For example, a, at, cat, cart and chart form a chain of 5 words.

Write longest_chain(words) that returns the number of words in the longest chain that uses only words from words. A single word is a chain of 1, and an empty list gives 0.

Examples

longest_chain(['a', 'at', 'cat', 'cart', 'chart', 'dog'])  # returns 5
longest_chain(['b', 'ab', 'abc', 'xyz', 'abcd'])           # returns 4
longest_chain(['tea', 'eat', 'ate'])                       # returns 1

The last example has no chain longer than one word: the three words have the same letters, but none is made from another by inserting a letter.

Constraints

  • 0 <= len(words) <= 60,000
  • Each word has 1 to 16 lowercase letters, and a word may appear more than once.

Time limit

Each test must finish within 10 seconds, and the hidden tests use lists of tens of thousands of words.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.