Longest String Chain

Info

Didn’t solve this problem bottom up, which would be faster.

• Worth thinking about a little bit and then checking the editorial for this.

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

• For every word, run DFS such that you remove every letter of that word one by one and see if it is in the words.
• If that word is in the words, then you know that you may go to the index + 1 (since you only removed 1 letter and so index + 1 exists), yet be careful here since there are multiple words with the same length (so index + 1 is not necessarily the predecessor with the letter chopped off).
• Therefore, you have to use .index() similar to Without Word Index, or otherwise use a word index: With Word Index.
• In the code, I did words.sort(key = lambda x: -len(x)) to sort in descending order of word length, so it would be index + 1 instead.

Cards

START Basic Front: Longest String Chain - LeetCode Back: words.sort(key = lambda x: -len(x), making sure to index to the correct position since there are many words of the same length.

END

Complexity

Runtime

$O(L^2\times N)$, where L is the length of the string, and we iterate through every character of every string within each recursion, and we run this DFS for every possible string in the outer for loop.

Space

$O(N)$ to store the words and word index.

Code

DP Optimization

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key = lambda x: -len(x))
        word_index = {}
        for i, word in enumerate(words):
            word_index[word] = i
 
        dp = {}
        n = len(words)
        def r(i):
            if i in dp:
                return dp[i]
 
            max_chain = 1
            for j in range(len(words[i])):
                pred = words[i][:j] + words[i][j+1:]
                if pred in words:
                    max_chain = max(max_chain, 1 + r(word_index[pred]))
 
            dp[i] = max_chain
            return max_chain
 
        max_chain = 0
        for i in range(len(words)):
            max_chain = max(max_chain, r(i))
        return max_chain

• This works since every word has a unique index (you are just going through every word in the list).

With Word Index

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key = lambda x: -len(x))
        word_index = {}
        for i, word in enumerate(words):
            word_index[word] = i
 
        dp = {}
        n = len(words)
        def r(i):
            if words[i] in dp:
                return dp[words[i]]
 
            max_chain = 1
            for j in range(len(words[i])):
                pred = words[i][:j] + words[i][j+1:]
                if pred in words:
                    max_chain = max(max_chain, 1 + r(word_index[pred]))
 
            dp[words[i]] = max_chain
            return max_chain
 
        max_chain = 0
        for i in range(len(words)):
            max_chain = max(max_chain, r(i))
        return max_chain

Without Word Index

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key = lambda x: -len(x))
        dp = {}
        n = len(words)
        def r(i):
            if words[i] in dp:
                return dp[words[i]]
 
            max_chain = 1
            for j in range(len(words[i])):
                pred = words[i][:j] + words[i][j+1:]
                if pred in words:
                    max_chain = max(max_chain, 1 + r(words.index(pred)))
 
            dp[words[i]] = max_chain
            return max_chain
 
        max_chain = 0
        for i in range(len(words)):
            max_chain = max(max_chain, r(i))
        return max_chain

Notes

---

References

Longest String Chain - LeetCode