# Longest String Chain
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-string-chain)
Canonical: https://scaleengineer.com/dsa/problems/longest-string-chain
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Flipkart](https://scaleengineer.com/companies/flipkart), [Wix](https://scaleengineer.com/companies/wix), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [MathWorks](https://scaleengineer.com/companies/mathworks), [Moloco](https://scaleengineer.com/companies/moloco), [Verily](https://scaleengineer.com/companies/verily)
---
## Problem
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.

**Constraints:**

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

# Approaches
## Brute-Force Depth First Search
This approach models the problem as finding the longest path in a graph. Each word is a node, and an edge exists from `wordA` to `wordB` if `wordA` is a predecessor of `wordB`. We perform a Depth First Search (DFS) from every single word to find the longest chain that can start with it. The overall maximum length found across all starting words is the answer. This method is highly inefficient because it recalculates the longest chain for the same words multiple times.
**Time:** O(N! * L) or worse. This is a loose upper bound, but it reflects the exponential nature of the algorithm due to redundant computations. For each call, we iterate through N words, and the recursion depth can be up to N. · **Space:** O(N * L), where N is the number of words and L is the maximum word length. This is for the recursion stack in the worst case of a chain involving all N words.
**Pros:** Conceptually simple and a direct translation of the problem definition.
**Cons:** Extremely inefficient due to massive re-computation of results for the same subproblems.; Will cause a 'Time Limit Exceeded' error on any non-trivial input size.
### Explanation
The algorithm works by exploring every possible chain exhaustively. The main function iterates through each word, treating it as a potential starting point. For each starting word, it calls a recursive DFS helper function, `dfs(currentWord)`. This function calculates the length of the longest chain starting with `currentWord` by iterating through all other words to find valid successors. A word `nextWord` is a successor if `currentWord` is its predecessor. If a successor is found, the function recursively calls itself with the successor to explore that path further. The lack of memoization means that `dfs(word)` will be computed from scratch every time it's called, even if the result for that word has been found before in a different recursive branch, leading to exponential complexity.

```java
class Solution {
    private String[] allWords;

    public int longestStrChain(String[] words) {
        this.allWords = words;
        int maxLen = 0;
        if (words == null || words.length == 0) return 0;
        for (String word : words) {
            maxLen = Math.max(maxLen, dfs(word));
        }
        return maxLen;
    }

    private int dfs(String currentWord) {
        int maxLength = 1;
        for (String nextWord : this.allWords) {
            if (isPredecessor(currentWord, nextWord)) {
                maxLength = Math.max(maxLength, 1 + dfs(nextWord));
            }
        }
        return maxLength;
    }

    private boolean isPredecessor(String wordA, String wordB) {
        if (wordA.length() + 1 != wordB.length()) {
            return false;
        }
        int i = 0; // pointer for wordA
        int j = 0; // pointer for wordB
        while (i < wordA.length() && j < wordB.length()) {
            if (wordA.charAt(i) == wordB.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == wordA.length();
    }
}
```
### Algorithm
*   Define a helper function `isPredecessor(wordA, wordB)` that returns true if `wordA` can be transformed into `wordB` by adding a single character.
*   Define a recursive function `dfs(currentWord)` that calculates the longest chain starting from `currentWord`.
*   Inside `dfs(currentWord)`:
    1.  Initialize `maxLength = 1` (for the word itself).
    2.  Iterate through every `nextWord` in the global list of words.
    3.  If `isPredecessor(currentWord, nextWord)` is true, it means `nextWord` can extend the chain.
    4.  Recursively call `dfs(nextWord)` and update the length: `maxLength = Math.max(maxLength, 1 + dfs(nextWord))`.
    5.  Return `maxLength`.
*   The main function initializes a global maximum length to 0.
*   It then iterates through every word in the input list, calling `dfs` for each one to treat it as a potential start of a chain.
*   The overall maximum length found is the answer.

## Top-Down Dynamic Programming with Memoization
This approach significantly improves upon the brute-force DFS by using memoization (a form of caching) to avoid re-computing results for the same subproblems. We use a hash map to store the length of the longest chain starting from each word. When the DFS function is called for a word, it first checks if the result is already in the cache. If so, it returns the cached value immediately, effectively pruning the search space and preventing redundant calculations.
**Time:** O(N * L^2). For each of the N words, we compute its result once. The computation involves a loop of size L (for insertion position), and inside it, string building (O(L)) and hash set lookup (O(L) due to string hashing). This gives a complexity of O(L^2) for each of the N states. · **Space:** O(N * L), where N is the number of words and L is the max word length. This space is used for the memoization map and the recursion stack.
**Pros:** Much faster than brute-force by eliminating redundant computations.; Guarantees that the subproblem for each word is solved only once.
**Cons:** The time complexity, while polynomial, can still be slow for the given constraints.; Deep recursion could lead to a stack overflow error if a very long chain exists.
### Explanation
The algorithm is a memoized version of the DFS approach. A `Map<String, Integer> memo` stores the results of `dfs(word)`, and a `Set<String> wordSet` provides fast word lookups. The main function calls `dfs(word)` for each word to ensure all possible chains are considered. The `dfs(currentWord)` function first checks the memoization table. If the result is not present, it calculates it by generating all possible successors (by inserting a character at each position), checking if they exist in the `wordSet`, and recursively calling `dfs` on them. The computed result is then stored in the memoization table to be reused later.

```java
import java.util.*;

class Solution {
    public int longestStrChain(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        Map<String, Integer> memo = new HashMap<>();
        int maxLen = 0;
        for (String word : words) {
            maxLen = Math.max(maxLen, dfs(word, wordSet, memo));
        }
        return maxLen;
    }

    private int dfs(String currentWord, Set<String> wordSet, Map<String, Integer> memo) {
        if (memo.containsKey(currentWord)) {
            return memo.get(currentWord);
        }

        int maxLength = 1;
        // Generate potential successors and check if they exist
        for (int i = 0; i <= currentWord.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                String successor = new StringBuilder(currentWord).insert(i, c).toString();
                if (wordSet.contains(successor)) {
                    maxLength = Math.max(maxLength, 1 + dfs(successor, wordSet, memo));
                }
            }
        }
        
        memo.put(currentWord, maxLength);
        return maxLength;
    }
}
```
### Algorithm
*   Use a `Map<String, Integer> memo` to store the computed results of the longest chain starting from a given word.
*   Use a `Set<String> wordSet` for fast lookups of words from the input array.
*   The main function iterates through all words, calling a recursive helper `dfs(word)` for each.
*   The `dfs(currentWord)` function is defined as follows:
    1.  Check if the result for `currentWord` is already in `memo`. If yes, return it.
    2.  Initialize `maxLength = 1`.
    3.  Generate all potential successors of `currentWord`. A successor is formed by inserting a character ('a' through 'z') at every possible position in `currentWord`.
    4.  For each generated `successor`, check if it exists in `wordSet`.
    5.  If it exists, recursively call `dfs(successor)` and update `maxLength = Math.max(maxLength, 1 + dfs(successor))`.
    6.  Store the final `maxLength` in `memo` before returning.

## Bottom-Up Dynamic Programming
This is the most efficient approach, utilizing bottom-up dynamic programming. It builds the solution iteratively by processing words from shortest to longest. By sorting the words by length, we ensure that when we calculate the longest chain for any given word, we have already computed the results for all of its potential, shorter predecessors. This avoids recursion and builds the solution from the ground up.
**Time:** O(N log N + N * L^2). The `O(N log N)` term comes from sorting the array. The main loop runs `N` times. Inside, we iterate `L` times to generate predecessors. String manipulation (e.g., `StringBuilder.deleteCharAt`) and hash map operations with string keys take `O(L)` time. This results in the `O(N * L^2)` term. · **Space:** O(N * L), where N is the number of words and L is the maximum word length, to store the `dp` map.
**Pros:** Most efficient time complexity among the approaches.; Iterative solution avoids recursion and the risk of stack overflow.; The logic is clean and directly builds towards the solution.
**Cons:** Requires an initial sorting step, which adds an O(N log N) factor to the complexity.; The space complexity is proportional to the number and length of words.
### Explanation
The algorithm begins by sorting the input `words` array by length. This is the key step that allows for a bottom-up approach. We use a hash map, `dp`, to store the length of the longest chain ending at each word. We iterate through the sorted words. For each `word`, we try to form a chain by finding a predecessor. A predecessor is one character shorter, so we generate all possible predecessors by deleting one character from the current `word`. Since the words are sorted by length, the `dp` value for any valid predecessor will have already been computed. We look up the predecessor's chain length in the `dp` map, add 1 (for the current word), and update the `dp` value for the current `word` with the maximum length found. The overall maximum is tracked and returned.

```java
import java.util.*;

class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        
        Map<String, Integer> dp = new HashMap<>();
        int maxChainLength = 0;
        
        for (String word : words) {
            int currentLongest = 1;
            for (int i = 0; i < word.length(); i++) {
                StringBuilder sb = new StringBuilder(word);
                String predecessor = sb.deleteCharAt(i).toString();
                
                int prevLength = dp.getOrDefault(predecessor, 0);
                currentLongest = Math.max(currentLongest, prevLength + 1);
            }
            dp.put(word, currentLongest);
            maxChainLength = Math.max(maxChainLength, currentLongest);
        }
        
        return maxChainLength;
    }
}
```
### Algorithm
*   Sort the `words` array based on the length of the strings in ascending order.
*   Create a hash map `dp` where `dp[word]` will store the length of the longest chain ending with that `word`.
*   Initialize a variable `maxChainLength = 0`.
*   Iterate through each `word` in the sorted array:
    1.  Initialize `currentLongest = 1` for the chain consisting of the `word` itself.
    2.  Generate all possible predecessors of the current `word` by deleting one character at each position.
    3.  For each generated `predecessor`, look up its longest chain length in the `dp` map: `prevLength = dp.getOrDefault(predecessor, 0)`.
    4.  Update the longest chain for the current word: `currentLongest = Math.max(currentLongest, prevLength + 1)`.
    5.  Store this result in the map: `dp.put(word, currentLongest)`.
    6.  Update the overall `maxChainLength = Math.max(maxChainLength, currentLongest)`.
*   Return `maxChainLength` after the loop.

# Solutions
### Java

```java
class Solution {
public
  int longestStrChain(String[] words) {
    Arrays.sort(words, Comparator.comparingInt(String : : length));
    int res = 0;
    Map<String, Integer> map = new HashMap<>();
    for (String word : words) {
      int x = 1;
      for (int i = 0; i < word.length(); ++i) {
        String pre = word.substring(0, i) + word.substring(i + 1);
        x = Math.max(x, map.getOrDefault(pre, 0) + 1);
      }
      map.put(word, x);
      res = Math.max(res, x);
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution { public: int longestStrChain ( vector < string >& words ) { sort ( words . begin (), words . end (), [ & ]( string a , string b ) { return a . size () < b . size (); }); int res = 0 ; unordered_map < string , int > map ; for ( auto word : words ) { int x = 1 ; for ( int i = 0 ; i < word . size (); ++ i ) { string pre = word . substr ( 0 , i ) + word . substr ( i + 1 ); x = max ( x , map [ pre ] + 1 ); } map [ word ] = x ; res = max ( res , x ); } return res ; } };
```

### Python

```python
class Solution:
    def longestStrChain(self, words: List[str]) -> int: def check(w1, w2): if len(w2) - len(w1) != 1: return False i = j = cnt = 0 while i < len(w1) and j < len(w2): if w1[i] != w2[j]: cnt += 1 else: i += 1 j += 1 return cnt < 2 and i == len(w1) n = len(words) dp = [1] * (n + 1) words . sort(key=lambda x: len(x)) res = 1 for i in range(1, n): for j in range(i): if check(words[j], words[i]): dp[i] = max(dp[i], dp[j] + 1) res = max(res, dp[i]) return res

```