1048. Longest String Chain

• cache the longest chain for each word
• find the max between longest chain of word, and longest chain when word has removed its ith character

class Solution:
    def longestStrChain(self, words: List[str]) -> int:

        dp = defaultdict(int)

        words.sort(key=len)

        globalMax = 0

        for word in words:
            dp[word] = 1

            for i in range(len(word)):
                preWord = word[:i] + word[i + 1:]
                dp[word] = max(dp[word], 1 + dp[preWord])

            globalMax = max(globalMax, dp[word])

        return globalMax