# 1048. Longest String Chain

"""
you are given an array of 'words' where each word consists of lowercase
english letters. 'word[a]' is a predecessor of 'word[b]' if and only if we
can insert exactly one letter anywhere in 'word[a]' without changing the
order of the other characters to make it equal to 'word[b]'. return the
length of the longest possible word chain with words chosen from the given
list of words.
"""


class Solution(object):
    def longestStrChain(self, words):
        dp = {}
        for w in sorted(words, key=len):
            dp[w] = max(dp.get(w[:i] + w[i + 1 :], 0) + 1 for i in xrange(len(w)))
        return max(dp.values())


if __name__ == "__main__":
    obj = Solution()
    print(obj.longestStrChain(["a", "b", "ba", "bca", "bda", "bdca"]))  # expect: 4
    print(obj.longestStrChain(["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]))  # expect: 5
    print(obj.longestStrChain(["abcd", "dbqca"]))  # expect: 1