⚡Flashcard Drill➔
NeetCode #692LC-1048Medium1-D Dynamic Programming
← Back to All Problems

#692 · #1048 · Longest String Chain(最长字符串链)

📌 Problem Statement & Constraints

Given an array of words, a word chain is a sequence where each word is a predecessor of the next, meaning the next word can be formed by inserting exactly one letter. Return the length of the longest possible word chain. Constraints: 1 <= words.length <= 1000, 1 <= words[i].length <= 16, and all words consist of lowercase English letters.

💡 Core Algorithmic Approaches

  1. Sort the words by length ascending, so every predecessor is processed before its successors.
  2. Let dp[w] be the length of the longest chain ending at word w.
  3. For each word, delete one character at a time to form candidate predecessors; if a candidate is in dp, extend it.
  4. The answer is the maximum dp value.

💻 Benchmark Python3 Implementation

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        dp = {}
        res = 1
        for w in words:
            best = 1
            for i in range(len(w)):
                prev = w[:i] + w[i + 1:]   # delete one character
                if prev in dp:
                    best = max(best, dp[prev] + 1)
            dp[w] = best
            res = max(res, best)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n * L^2): for each word, L deletions each building an O(L) slice.
💾 Space Complexity
O(n * L) for the dictionary keys.

⚠️ Interview Pitfalls & Follow-ups

  • Sorting by length descending: predecessors must come first, so ascending length is required.
  • Comparing every pair for a one-letter difference: that is O(n^2 * L) and unnecessary; deleting one character per word is O(n * L^2).
  • Forgetting the base case: a single-letter word has no predecessor in the dictionary, so best starts at 1.
  • Assuming chains are contiguous in the input: the input order is irrelevant; only lengths matter.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems