# 1048. Longest String Chain

# Question link is here.

# Question

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example 1:

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

Example 2:

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"].

Example 3:

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.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of lowercase English letters.

# Solution

There is one thing that needs to pay attention. THe longest chain does not require to be continuous. It needs to be the longest possible word chain with words chosen from the given list of* words.

Therefore, for any word w, if it doesn't have predecessor, the longest word chain endding with this word is '1', otherwise, it is max(predecessor's word chain length) + 1.

Now, we can see this problem is a typical DP problem. And all we need to do now is to find a way to determine if word1 is word2's predecessor.

In my opinion, there are to ways to do that.

# Method1 use hashtable to check
for i in range(len(word)):
  predecessor = word[:i] + word[i+1:]
  if predecessor in hashmap.keys():
    return True
return False

#Method2 check each char one by one
    def isPredecessor(self, word1, word2):
        if len(word1) + 1 != len(word2):
            return False
        flag = True
        index1 = 0
        index2 = 0
        while index1 < len(word1):
            if word1[index1] == word2[index2]:
                index1 += 1
                index2 += 1
            else:
                if not flag:
                    return False
                index2 += 1
                flag = False
        return True

These two method both have time complexity of $O(L)$ where $L=len(word)$

And now the solution is obvious:

class Solution: #using method 1
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key = lambda x:len(x)) #nlogn
        max_word_length = len(words[-1]) 
        length_hashmap = defaultdict(list)
        word_max_chain_cnt = defaultdict(int)
        for word in words: #n
            length_hashmap[len(word)].append(word)
            word_max_chain_cnt[word] = 1
        res = 1
        for word in words:  #n
            for i in range(len(word)): #L
                predecessor = word[:i] + word[i+1:]
                if predecessor in word_max_chain_cnt.keys():
                    word_max_chain_cnt[word] = max(word_max_chain_cnt[word], word_max_chain_cnt[predecessor] + 1)
            res = max(res, word_max_chain_cnt[word])
        return res
         
        #Ln^2

The time complexity for this is nlog for sorting, n for init the dictionary, nL for thoes two loops. Therefore, the over all time complexity is $O(nlog + nl)$

class Solution: #using method 2
    def isPredecessor(self, word1, word2):
        if len(word1) + 1 != len(word2):
            return False
        flag = True
        index1 = 0
        index2 = 0
        while index1 < len(word1):
            if word1[index1] == word2[index2]:
                index1 += 1
                index2 += 1
            else:
                if not flag:
                    return False
                index2 += 1
                flag = False
        return True
            
    
    
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key = lambda x:len(x)) #nlogn
        max_word_length = len(words[-1]) 
        length_hashmap = defaultdict(list)
        word_max_chain_cnt = defaultdict(int)
        for word in words: #n
            length_hashmap[len(word)].append(word)
            word_max_chain_cnt[word] = 1
        res = 1
        for word in words:
            if len(word)-1 in length_hashmap.keys():
                for predecessor in length_hashmap[len(word) - 1]: #O(L)
                    if self.isPredecessor(predecessor, word):
                        word_max_chain_cnt[word] = max(word_max_chain_cnt[word], word_max_chain_cnt[predecessor] + 1)
                res = max(res, word_max_chain_cnt[word])
        return res

The time complexity is $O(n^2L)$

Leetcode 1048

Longest String Chain

# 1048. Longest String Chain

# Question link is here.

# Question

# Solution