# Longest String Chain

Published: Jan 19, 2023

Medium Hash Table Two Pointers String

## Problem Description

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

`word[A]` is a predecessor of `word[B]` if and only if we can insert exactly one letter anywhere in `word[A]` without changing the order of the other characters to make it equal to `word[B]`.

For example, “abc” is a predecessor of “abac”, while “cba” is not a predecessor of “bcad”. A 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. 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.

Constraints:

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

https://leetcode.com/problems/longest-string-chain/

## Examples

``````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.
``````

## How to Solve

To create a path, a successor is one character longer to its predecessor and additional one character can be any. Create one character shorter words and check if those are in the word list. If exists, a path by two words is found. While checking predecessors, count up the path. In the end, the maximum length path will be found.

## Solution

``````class LongestStringChain {
public:
int longestStrChain(vector<string>& words) {
sort(words.begin(), words.end(),
[](const string w1, const string w2) {
return w1.size() < w2.size();
});
int max_path = 1;
unordered_map<string, int> counter;
for (string word : words) {
int path = 1;
for (int i = 0; i < word.size(); ++i) {
string pred = word.substr(0, i) + word.substr(i + 1, word.length() + 1);
if (counter.count(pred) != 0) {
path = max(path, counter[pred] + 1);
}
}
counter[word] = path;
max_path = max(max_path, path);
}
return max_path;
}
};
``````
``````
``````
``````
``````
``````class LongestStringChain:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=lambda x: len(x))
max_path, counter = 1, {}
for word in words:
path = 1
for i in range(len(word)):
pred = word[:i] + word[i + 1:]
if pred in counter:
path = max(path, counter[pred] + 1)
counter[word] = path
max_path = max(max_path, path)
return max_path
``````
``````
``````

## Complexities

• Time: `O(n * log(n) + n * m)` – n: number of words, m: length of a word. It could be `O(1)` considering constraints.
• Space: `O(n * m)` – It could be `O(1)` since n * m is at most 1000 * 16 (constant).