Longest String Chain - Leetcode Solution

The Longest String Chain problem on LeetCode is a dynamic programming problem that requires finding the longest chain of words in a given list such that each word in the chain is formed by deleting one letter from the previous word.

To solve this problem, we can first sort the words based on their lengths. We can then build a dictionary of words where the key is the word itself and the value is the length of the longest chain that can be built starting from this word.

For each word in the list, we can delete one letter at a time and check if the resulting word is in our dictionary. If the resulting word is in the dictionary, we can update its chain length value by taking the maximum value of the current chain length and adding one to it.

We can repeat this process for all the words in the list and return the maximum value in the dictionary.

The time complexity of this solution is O(n*w^2), where n is the number of words in the list and w is the maximum length of a word in the list. This is because we iterate through each word and for each word, we delete each of its letters and check if the resulting word is in our dictionary.

Here is the Python code for the solution:

def longestStrChain(words):
    words.sort(key=len)
    word_dict = {}
    max_chain_len = 1
    
    for word in words:
        word_dict[word] = 1
        for i in range(len(word)):
            new_word = word[:i] + word[i+1:]
            if new_word in word_dict:
                word_dict[word] = max(word_dict[word], word_dict[new_word]+1)
        max_chain_len = max(max_chain_len, word_dict[word])
    
    return max_chain_len

We start by sorting the words in the list based on their lengths. We then initialize an empty dictionary to store the chain length values for each word and set the maximum chain length to 1.

For each word in the list, we set its chain length value in the word_dict to 1. We then iterate through each letter in the word and delete it to create a new_word. If the new_word is in our dictionary, we update the chain length value for the current word by taking the maximum value of its current chain length and adding one to the chain length of the new_word.

We update the max_chain_len variable with the maximum chain length value seen so far and return it at the end of the loop.

1