Longest String Chain (LC 1048)

Problem Statement

Given an array of words, word A is a predecessor of word B if you can insert exactly one letter anywhere in A to make it equal to B. A word chain is a sequence where each word is a predecessor of the next.

Return the length of the longest possible word chain.

Example 1:

Input:  words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: "a" -> "ba" -> "bda" -> "bdca".

Example 2:

Input:  words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: "xb" -> "xbc" -> "cxbc" -> "pcxbc" -> "pcxbcf".

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] consists of lowercase letters.

Difficulty: Medium

---

Pattern Recognition

• Input structure: array of strings, varying lengths.
• What are we optimizing? longest chain under the "insert one char" relation.
• Pattern: DP over words sorted by length. For each word, try every predecessor (word with one char removed) and take max dp[pred] + 1.
• Why: the relation is length-monotone — a predecessor is always one character shorter. Sorting by length gives a DAG processing order, and trying all |word| single-deletions takes O(L) per word.

---

Approach

Brute Force

For each pair (A, B), check if A is a predecessor of B (O(L^2) per pair). O(n^2 * L^2). Slow at n = 1000.

Optimal — Sort + DP with One-Char-Deletion Lookup

Key Insight: Rather than testing every word pair, enumerate each word's possible predecessors by deleting each character. There are only |word| of them — O(L) per word. Use a hash map dp: word -> longest chain ending at word.

Steps:

1. Sort words by length ascending.
2. dp = {}.
3. For each word in sorted order:
   • best = 1 (chain of length 1 is the word itself).
   • For each i in 0..|word|-1:
     • predecessor = word[:i] + word[i+1:]
     • If predecessor in dp: best = max(best, dp[predecessor] + 1).
   • dp[word] = best.
4. Return max(dp.values()).

Time: O(n log n + n * L^2) — sorting plus n words times L deletions times L per substring construction. Space: O(n + L * n) for the map (substring keys).

---

Walkthrough

words = ["a","b","ba","bca","bda","bdca"].

Sort by length: ["a", "b", "ba", "bca", "bda", "bdca"].

word	predecessors tried	dp lookups	dp[word]
"a"	""	—	1
"b"	""	—	1
"ba"	"a", "b"	dp[a]=1, dp[b]=1	2
"bca"	"ca", "ba", "bc"	dp[ba]=2	3
"bda"	"da", "ba", "bd"	dp[ba]=2	3
"bdca"	"dca", "bca", "bda", "bdc"	dp[bca]=3, dp[bda]=3	4

Return 4.

---

Implementation

TypeScript

function longestStrChain(words: string[]): number {
    words.sort((a, b) => a.length - b.length);
    const dp = new Map<string, number>();
    let best = 1;
    for (const word of words) {
        let longest = 1;
        for (let i = 0; i < word.length; i++) {
            const predecessor = word.substring(0, i) + word.substring(i + 1);
            if (dp.has(predecessor)) {
                longest = Math.max(longest, dp.get(predecessor)! + 1);
            }
        }
        dp.set(word, longest);
        best = Math.max(best, longest);
    }
    return best;
}

C++

int longestStrChain(vector<string>& words) {
    sort(words.begin(), words.end(),
         [](const string& a, const string& b) { return a.size() < b.size(); });
    unordered_map<string, int> dp;
    int best = 1;
    for (auto& word : words) {
        int longest = 1;
        for (int i = 0; i < (int)word.size(); i++) {
            string pred = word.substr(0, i) + word.substr(i + 1);
            auto it = dp.find(pred);
            if (it != dp.end()) longest = max(longest, it->second + 1);
        }
        dp[word] = longest;
        best = max(best, longest);
    }
    return best;
}

Watch out:

1. Not sorting by length first means you might query dp[predecessor] before you computed it.
2. Building the predecessor string inefficiently (repeated concatenation in a loop) creates O(L^2) per word — still within budget but worth noting for very long strings.
3. Using a sorted array and indexOf instead of a hash map blows up to O(n) per lookup; always use a map.

---

Complexity Analysis

	Time	Space
Brute Force pair-compare	O(n^2 * L^2)	O(n)
DP + deletion keys	O(n log n + n * L^2)	O(n * L)

Bottleneck: you construct L substring keys per word, each of size L, giving O(n * L^2) — much better than the pairwise O(n^2 * L^2).

---

Edge Cases

1. Single word — chain length 1.
2. All same length — no valid predecessor relation; answer is 1.
3. Many duplicates of the same word — sort places them together; dp[word] is computed once but written repeatedly harmlessly.
4. Chain uses every word — sorting by length preserves the natural order.
5. Words with length 1 — predecessors are the empty string; just skip the lookup.
6. Words of length up to 16 — each produces up to 16 substring keys; tiny.

---

Related Problems

• LC 300 — Longest Increasing Subsequence — 1D version: dp[i] depends on dp[j] for j < i.
• LC 1312 — Minimum Insertion Steps to Make a String Palindrome — Different problem, same "add one character" flavor.
• LC 368 — Largest Divisible Subset — Sort + DP with predecessor chain; identical skeleton.
• LC 646 — Maximum Length of Pair Chain — Greedy-by-end or DP; similar length-extension pattern.

---

What Is Expected at Each Level

Junior: Attempts brute force. With guidance, arrives at sorted-by-length DP.

Mid-level: Implements the deletion-key DP cleanly, explains O(n * L^2), handles duplicate words gracefully.

Senior (L4 target): Writes the solution quickly, discusses the DAG structure implied by length monotonicity, contrasts with LC 368 (divisibility chains use the same skeleton), and notes that the substring construction could be replaced with a rolling hash if L grows.