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.

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.

Let’s tackle the Longest String Chain problem from zero to hero with our six-phase Dynamic Programming approach:

Explain the problem in simple terms
Draw the decision tree (visualize the recursion)
Implement recursion + memoization (top-down)
Implement tabulation (bottom-up)
Optimize space complexity (if possible)
Analyze time complexity at each level of optimization

Problem Statement

We’re given an array of words. We say that a word A is a predecessor of word B if by removing exactly one letter from B, we can get the word A. The order of letters in B must remain the same apart from the removal of that single letter. Formally:

A is a predecessor of B if A can be formed by removing exactly one character from B without reordering the other characters.

A word chain is a sequence of words [w1,w2,...,wk] such that each word is a predecessor of the next: w1→w2→...→wk. We want to find the length of the longest possible word chain that can be built from the given list of words.

Example:
If the input array is ["a","b","ba","bca","bda","bdca"], the longest chain is ["a","ba","bda","bdca"]. The length of this chain is 4.

1️⃣ Explain the Problem in Simple Terms

We have a list of words.
We can link word A to word B if A is a “predecessor” of B, i.e., B can be formed by inserting exactly one character into A at the appropriate position. (Equivalently, A can be formed by removing one character from B.)
We want to arrange some of these words in a sequence (chain) where each word is the predecessor of the next.
We need the longest such chain possible and return the length (number of words in it).

2️⃣ Draw the Decision Tree (Recursive Structure)

Imagine each word as a node in a directed graph, where there’s an edge A→B if A is a predecessor of B. Then the problem becomes finding the longest path in this directed acyclic graph (DAG), because words have strictly increasing length and you can’t go backward.

If we do naive recursion, we’d pick a word, try to find all words that can follow it, and so on. For a word w, its neighbors are all words that are formed by adding exactly one character to w.

A simplified decision tree might look like this:

                       "a"
                     /     \
                 "ba"       "ab"? (if existed)
                  |          ...
               "bda"       
                /    \
            "bdca"    "bdxa"? (if existed)
              ...

Each path is a chain. Our goal is to find the path with maximum length.

3️⃣ Implement Recursion + Memoization (Top-Down)

Key Idea

Sort the words by their lengths.
- Why? Because if w1 is a predecessor of w2, then len(w1) = len(w2) - 1. We only need to check possible successors that are exactly 1 character longer.
Precompute for each word, a set/dictionary lookup for quick checks: “Does a word candidate exist in the list?”
Recursive function longestChain(word) → returns the length of the longest chain ending with word.
- We try all possible ways to insert one letter into some smaller word to form word, equivalently: to get a predecessor, we remove one letter from word and see if the resulting string is in our list.
- Then longestChain(word) = 1 + max(longestChain(predecessor)) over all valid predecessors.
Use a memo to avoid recomputing longestChain(word).

Step-by-Step JS Code

/**
 * @param {string[]} words
 * @return {number} The length of the longest string chain
 */
function longestStrChainMemo(words) {
  // 1. Sort words by length
  words.sort((a, b) => a.length - b.length);

  // 2. Put all words into a set for fast existence checks
  const wordSet = new Set(words);

  // 3. Memo to store the longest chain ending at a specific word
  //    key: word, value: length of longest chain ending with this word
  const memo = new Map();

  // Helper function to compute longest chain ending in "word"
  function dfs(word) {
    // If we already computed it, return from memo
    if (memo.has(word)) {
      return memo.get(word);
    }

    // The chain has at least length 1 (the word itself)
    let best = 1;

    // Try removing one character from "word" in all possible ways
    // to see if the resulting string is a predecessor
    for (let i = 0; i < word.length; i++) {
      const predecessor = word.slice(0, i) + word.slice(i + 1);

      // If the predecessor is in our list, we can form a chain
      if (wordSet.has(predecessor)) {
        const candidateLength = 1 + dfs(predecessor);
        best = Math.max(best, candidateLength);
      }
    }

    memo.set(word, best);
    return best;
  }

  // 4. We want the longest chain among all words
  let answer = 0;
  for (const w of words) {
    answer = Math.max(answer, dfs(w));
  }

  return answer;
}

Explanation

After sorting, dfs(w) checks all possible one-character deletions from w to find a shorter word.
If that shorter word is in our list, we recursively find its chain length.
We store the result in memo so each word is computed once.
We take the max across all words for the final answer.

4️⃣ Implement Tabulation (Bottom-Up)

We can also do this bottom-up. The logic is similar: if we process words from shortest to longest, when we get to a word, we already know the best chain lengths for all shorter words.

Steps

Sort words by length ascending.
Create a HashMap dp from word → best chain length ending with that word. Initially, each word can form a chain of at least length 1.
For each word (from shortest to longest):
- Generate all possible predecessors by removing one character.
- If predecessor is in dp, then dp[word] = max(dp[word], dp[predecessor] + 1).
The answer is the max value in dp.

JavaScript Code

/**
 * @param {string[]} words
 * @return {number}
 */
function longestStrChainTab(words) {
  // 1. Sort words by length
  words.sort((a, b) => a.length - b.length);

  // 2. dp: Map each word to the length of the longest chain ending with it
  const dp = new Map();

  let answer = 1; // There's at least a chain length of 1 if we have at least one word

  for (const word of words) {
    // By default, the chain ending with 'word' has length 1 (itself)
    dp.set(word, 1);

    // 3. Check all possible predecessors by removing one character
    for (let i = 0; i < word.length; i++) {
      const predecessor = word.slice(0, i) + word.slice(i + 1);

      // If the predecessor exists in dp, update dp[word]
      if (dp.has(predecessor)) {
        const newLength = dp.get(predecessor) + 1;
        dp.set(word, Math.max(dp.get(word), newLength));
      }
    }

    // Update global answer
    answer = Math.max(answer, dp.get(word));
  }

  return answer;
}

5️⃣ Optimize Space Complexity (If Possible)

In this problem, each word can’t be easily replaced by a smaller state because:

We rely on quick existence checks and direct mapping from string → chain length.
We do need to store the entire dp mapping from word to best chain length, which is O(n) space if n is the number of words.

We cannot trivially reduce that below O(n), because each word might have a unique chain length. Also, storing them in a HashMap is essential.

We can’t easily do “rolling arrays” or similar since the state is a string, not an integer index. So the space complexity is effectively O(n) for storing the DP results. That’s already as good as it gets for this problem (aside from the memory for storing the input itself).

6️⃣ Analyze Time Complexity at Each Level

Sorting: We sort n words, and if we assume average word length is k, sorting is O(nlog⁡n×k) if comparisons are length-based or O(nlog⁡n) if we just rely on built-in sorting and short-circuit comparisons.
Tabulation: For each word, we try removing each of its characters (up to k), forming a predecessor in O(k) time, then do a dp.has(predecessor) check in O(1) average for a HashMap. So for each word, that’s O(k2) in the worst case (building each predecessor in O(k) and we do it k times). Summed over n words, it’s O(n⋅k2).
- If the words vary in length, let’s define k=max⁡word length.
Memoized recursion has a similar complexity. Each word is computed once, and each computation tries up to kdeletions. Each deletion is O(k) to create the substring. So each word’s DFS is O(k2). For n words, that’s O(n⋅k2)plus sorting overhead.

Hence, the final time complexity is typically stated as O(nlog⁡n+n⋅k2) or O(n⋅k2) if n is large and sorting is overshadowed by the chain building.

Final Overview

Longest String Chain can be approached in two main ways:

Recursion + Memoization
- We compute dfs(word), which is 1 plus the max of dfs(predecessor) for all valid predecessors.
- We store results in a map so each word is computed once.
Tabulation (Bottom-Up)
- Sort words by length, from shorter to longer.
- Maintain dp[word] = 1 initially, then for each word, we try removing each letter to see if there’s a known predecessor.
- Update dp[word] = max(dp[word], dp[predecessor] + 1).

Both solutions revolve around the same logic of checking all one-letter deletions. The tabulation version is often shorter code and is a popular approach in interviews.

Space optimization beyond O(n) for the DP mapping is not feasible here, because we need a separate state entry for each distinct word. The best we can do is store the results in a single map (which we do).

Time complexity is O(n⋅k2) for the DP portion, plus O(nlog⁡n) for sorting, where k is the maximum word length.

With that, you should have a robust step-by-step solution for the Longest String Chain problem!

Longest String Chain