pyassistant

Longest Word Deletion Chain

Given a list of distinct lowercase words, find the length of the longest chain of words where each word in the chain is formed by deleting exactly one character from the previous word. Deletions may remove any single character (not necessarily contiguous). The chain must consist entirely of words from the given list. Return the maximum possible length of such a chain. If the list is empty, return 0. Constraints: words length up to about 1000 and word lengths up to about 1000, so aim for an approach roughly O(N * L^2) or better where N is number of words and L is average word length.

Example:

Input:
['a', 'b', 'ba', 'bca', 'bda', 'bdca']
Output:
4

Make sure you return your solution, don't print!

AI

Bot

Trying to solve my challenge? Ask if you must, or press the purple button so I can analyze your code.