Longest String Chain Python Solution

lcpy gen -n 1048   # by problem number
lcpy gen -s longest_string_chain   # by problem name

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

class Solution:
    # Time: O(n * L^2) where L is the max word length
    # Space: O(n * L)
    def longest_str_chain(self, words: list[str]) -> int:
        words = sorted(words, key=len)
        chains: dict[str, int] = {}
        best = 0
        for word in words:
            chains[word] = 1
            for i in range(len(word)):
                predecessor = word[:i] + word[i + 1 :]
                if predecessor in chains:
                    chains[word] = max(chains[word], chains[predecessor] + 1)
            best = max(best, chains[word])
        return best