Longest String Chain (Leetcode 1048)

Difficulty: Medium Link: Day 17: May Leetcode Challenge

Problem Description

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2word_2 is a predecessor of word_3, and so on.

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

Examples

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chain is "a","ba","bda","bdca".
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5

Constraints

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

Solution

We can identify a pattern that length of every string in the chain increases progressively, so if current element is “abc” and the next element will have to be of length Length(abc) + 1 = 4.  A key point in the problem statement is that word1 can be a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. In other words, word2 should have one letter more than word1 and the position of this new letter can be anywhere. Note that the order of words need not to be maintained.

One tricky thing is that if we build our solution on the definition of the predecessor intuitively then it would be difficult. Take an example, to check “ab” is a predecessor of “acb”, we will have to split the string and try every possible combination of alphabet if they match. “ab” = {a-z} + “ab” , “a” + {a-z} + “b” , “ab” + {a-z}. If the character space increases, it increases the complexity. What if we reverse the definition? For “acb” to be a successive chain in the link, we can remove every character one by one and match it with “ab”. This is simple an O(L) operation.

Dynamic Programming

We can think of the string chains as graph thus there are multiple chains possible but we will have to only find the maximum chain length. Suppose that chain is currently “a” -> “ab” -> “adb” which is of length 3. Now if we encounter “acdb” we can observe that the maximum length = previous max length + 1. Similarly this problem can be further broken down into subproblems until we reach a single string “a”. For any individual string, the maximum chain length would be 1.

What we can do is whenever we encounter a new word, we will find all possible sequences with this word as the last word in the sequence. Then, we will store the length of the longest possible sequence that ends with this word.

We will use a map for this where each key will be an ending word and the value will be the length of the longest possible word sequence ending with this word. In the above example when we first encounter the word ab we will store the value 2 (word sequence ab -> b) for key ab. The next time we encounter ab, we will simply return the value stored against it in the map instead of going through the entire subtree again. This process is known as memoization and it prevents recalculation. For every word present in the list, we only need to determine the length of the longest path that ends with this word once.

Bottom Up Approach (Tabulation)

The length of the words in a sequence increases as we move from left to right. If we can sort the words in ascending order based on their length, we can be sure that the next word in the list would be greater length than the current word. Next, we can iterate over the sorted list and calculate the length of the longest sequence possible where the word at index i is the end word. How we calculate the possible predecessors is we remove one character from the string one by one and check if the resulting string already has contributed in the chain. We store this result in a map where key is the word and value is the sequence length. By doing this we ensure that, for each word that we encounter, we already know the result of all of its possible predecessors. 

Top-Down (Memoization)

We can follow the same approach of deleting one character from a word one by one in a recursive manner. Here, we would not need a sorted list by length since we would be recursively solving and saving it an a table. We will the logic for checking combinations in a functions and call it for every word while maintaining the max length observed yet.

Code

Swift : Bottom Up

class Solution {
func longestStrChain(_ words: [String]) -> Int {
guard words.count > 1 else { return words.count}
let words = words.sorted(by: { word1, word2 in
return word1.count < word2.count
})
var map = [String:Int]()
var maxLength = 0
for word in words{
var currentMax = 1
for j in 0..<word.count {
var wordCopy = word
wordCopy.remove(at: word.index(word.startIndex, offsetBy:j))
if let existingLength = map[wordCopy] {
currentMax = max(currentMax, existingLength + 1)
}
}
map[word] = currentMax
maxLength = max(maxLength, currentMax)
}
return maxLength
}
}

Swift : Top-Down (Memoization)

class Solution {
func longestStrChain(_ words: [String]) -> Int {
guard words.count > 1 else { return words.count }
var map = [String:Int]()
var maxLength = 0
let wordSet = Set(words)
for word in wordSet{
let chainLength = dfs(wordSet, &map, word)
maxLength = max(chainLength, maxLength)
}
return maxLength
}
func dfs(_ words:Set<String>, _ map :inout [String:Int], _ str:String) -> Int {
if let cachedLength = map[str] {
return cachedLength
}
var maxLength = 1
for i in 0..<str.count{
var word = str
let index = word.index(word.startIndex,offsetBy: i)
word.remove(at:index)
if words.contains(word){
let currentLength = 1 + dfs(words,&map, word)
maxLength = max(maxLength, currentLength)
}
}
map[str] = maxLength
return maxLength
}
}

Python: Bottom Up

class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len) # sort words by its length
ans = 0
cnt = defaultdict(int)
for word in words:
cnt[word] = 1
for i in range(len(word)):
predecessor = word[:i] + word[i+1:]
if predecessor in cnt and cnt[word] < cnt[predecessor] + 1:
cnt[word] = cnt[predecessor] + 1
ans = max(ans, cnt[word])
return ans

Java: Bottom Up

class Solution {
public int longestStrChain(String[] words) {
Map<String, Integer> dp = new HashMap<>();
// Sorting the list in terms of the word length.
Arrays.sort(words, (a, b) > a.length() b.length());
int longestWordSequenceLength = 1;
for (String word : words) {
int presentLength = 1;
// Find all possible predecessors for the current word by removing one letter at a time.
for (int i = 0; i < word.length(); i++) {
StringBuilder temp = new StringBuilder(word);
temp.deleteCharAt(i);
String predecessor = temp.toString();
int previousLength = dp.getOrDefault(predecessor, 0);
presentLength = Math.max(presentLength, previousLength + 1);
}
dp.put(word, presentLength);
longestWordSequenceLength = Math.max(longestWordSequenceLength, presentLength);
}
return longestWordSequenceLength;
}
}

Complexity Analysis

Sorting a list of size N takes O(NLogN) time. We iterate over the words list and try matching the characters by deleting one by one which takes O(L2). The word operation is O(L2) because first we iterate over the word length to remove characters, ie O(L) and for every iteration we try to build remainder string which is O(L) itself, hence O(L2).Therefore, total time complexity increases to O(NLogN) + O(L2).

For space, maximum of N words can be stored, hence it is linear.

Time = O(NLogN) + O(L2) // Where N is the number of words and L is the length of each word

Space = O(N)

Links

Dynamic Programming | Free Code Camp

Bottom Up Dynamic Programming

Leave a Reply

Your email address will not be published. Required fields are marked *