DSA problem
Longest String Chain
You are given an array of words. A word a is a predecessor of a word b if and only if you can insert exactly one letter anywhere in a to make it equal to b. For example, "abc" is a predecessor of "abac" (insert a between a and b).
A word chain is a sequence of words [w1, w2, ..., wk] such that w1 is a predecessor of w2, w2 is a predecessor of w3, and so on. A single word is itself a valid chain of length 1. Return the length of the longest possible chain that can be formed from the given words.
This problem is structurally an LIS variant where the ordering is "predecessor of" rather than "less than." Since every predecessor must be exactly one character shorter, words can only chain across strictly increasing lengths. Sorting the array by length puts every predecessor strictly before its successors in the iteration order, so we can fill a DP table in a single pass.
The clean approach uses a hash map dp from each word to the best chain length ending at that word. For each word w taken in length-sorted order, try removing every one of its characters to form a candidate predecessor p; if p is in dp, then dp[w] = max(dp[w], dp[p] + 1). Generating all single-character deletions is O(L) substring work per word, and there are at most n words of length up to L, giving O(n * L²) overall. The answer is the maximum value across all dp entries.
Examples
words = ["a","b","ba","bca","bda","bdca"]4words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]5words = ["abcd","dbqca"]1Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 16
- words[i] consists of lowercase English letters only.
- The chain ordering is by predecessor (insert exactly one character), not by lexicographic order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.