# 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_2``word_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.

## 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)