# 1048 Leetcode Solution Using JavaScript

## Table of contents

### The question we received:

You are given an array of `words`

where each word consists of lowercase English letters.

`word<sub>A</sub>`

is a **predecessor** of `word<sub>B</sub>`

if and only if we can insert **exactly one** letter anywhere in `word<sub>A</sub>`

**without changing the order of the other characters** to make it equal to `word<sub>B</sub>`

.

- 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<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>]`

with `k >= 1`

, where `word<sub>1</sub>`

is a **predecessor** of `word<sub>2</sub>`

, `word<sub>2</sub>`

is a **predecessor** of `word<sub>3</sub>`

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

.

Here is one way to solve Longest String Chain problem:

```
const longestStrChain = (words) => {
const wordSet = new Set(words); // Store words in Set
const cache = {}; // Cache for chain lengths
let maxLength = 0; // Track max length
for (let i = 0; i < words.length; i++) {
const currWord = words[i]; // Current word
let currMaxLength = findChainLength(currWord, wordSet, cache); // Find chain length
maxLength = Math.max(maxLength, currMaxLength); // Update max
}
return maxLength; // Return result
}
const findChainLength = (word, wordSet, cache) => {
if (cache[word]) { // If cached, return
return cache[word];
}
let maxLength = 1; // Start with length 1
for (let i = 0; i < word.length; i++) {
const predecessor = word.slice(0, i) + word.slice(i + 1); // Generate predecessor
if (wordSet.has(predecessor)) { // If predecessor is valid
const length = findChainLength(predecessor, wordSet, cache) + 1; // Recursive call
maxLength = Math.max(maxLength, length); // Update max
}
}
cache[word] = maxLength; // Cache result
return maxLength;
}
```

**Explanation**

We use a Set to quickly lookup if a predecessor word exists.

A cache stores the longest chain ending at each word, to avoid recomputing.

We iterate through each word, recursively finding its predecessor chains.

We continually update the maxLength found.

Storing chain lengths in the cache allows us to incrementally build up the optimal solution.

**What is a predecessor?**

The word X is a predecessor of the word Y if we can insert exactly one new letter into X without reordering the other letters, to make it equal to Y.

For example:

"a" is a predecessor of "ba"

"hat" is a predecessor of "that"

A single word by itself forms a trivial chain of length 1.

**Complexity**

Time: O(N x M^2), where N is the number of words, and M is the max word length.

Space: O(N), to store cache.

This bottom-up dynamic programming approach allows us to efficiently find the longest valid word chain.

**Example Walkthrough**

Let's walk through a simple example to see how this would work:

Input: `["a", "b", "ba", "bca", "bda", "bdca"]`

Starting with "a", its chain length is 1.

"b" also has a chain of 1.

For "ba", its predecessor is "a", so the chain is 1 + 1 = 2.

"bca" has the predecessor "ba", so the chain is 2 + 1 = 3.

"bda" has predecessor "bca", chain is now 3 + 1 = 4.

Finally, "bdca" chains to "bda", making the full chain length 4 + 1 = 5.

The maximum chain formed is of length 5.

If you have any query kindly comment down

I hope you have understand the logic and solution that i want to explain