Problem statement

https://leetcode.com/problems/longest-string-chain/

Solution

The idea in this problem is to start from the longest word and find an answer for this word using the answers for smaller words. For example if we have word apple, then we need to check if we have words pple, aple, appe, appl in our list of words. To make it work fast we need to put all words into set: set_words = set(words). Then all we need to do is to check all words with one letter removed.

Complexity

Time complexity is O(n*L*L), where n is number of words and L is the biggest length of the word: for word of length L we need to check L-1 candidates, all of them with length L-1. Space complexity is L(n*L*L), because we actually keep a lot of neighbors of our words in lru cache.

Code

class Solution:
    def longestStrChain(self, words):
        set_words = set(words)
        
        @lru_cache(None)
        def dp(word):
            if word not in set_words: return 0
            return max(dp(word[:i] + word[i+1:]) for i in range(len(word))) + 1
           
        return max(dp(word) for word in words)

Update

There is update from @rkmd with O(n*L) space complexity

def dp(word):
    return max((dp(test) for i in range(len(word)) if (test := word[:i] + word[i+1:]) in set_words), default=0) + 1