Connecting Words into Chains | Longest String Chain Algorithm

The question we received:

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.

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

1048 Leetcode Solution Using JavaScript

Table of contents

The question we received:

Explanation

What is a predecessor?

Complexity