1048. Longest String Chain

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