Skip to main content

1048 - Longest String Chain

Difficulty: Medium | Pattern: Dynamic Programming | Company tags: Amazon, Facebook, Google

Problem Statement​

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 you can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

  • E.g., "abc" is a predecessor of "abac".

A word chain is a sequence of words 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

Algorithm Flow​

Approach: DP with Word Hashing — O(n × L²)​

Key insight: Sort words by length. For each word, try removing one character at a time — if the resulting word exists in our DP map, it could be the predecessor. Track the longest chain ending at each word.

def longestStrChain(words: list[str]) -> int:
    words.sort(key=len)
    dp = {}  # word → longest chain ending here
    best = 1
    
    for word in words:
        dp[word] = 1  # at minimum, chain of length 1
        
        for i in range(len(word)):
            prev = word[:i] + word[i+1:]  # remove character at index i
            if prev in dp:
                dp[word] = max(dp[word], dp[prev] + 1)
        
        best = max(best, dp[word])
    
    return best

Dry Run​

words = ["a","b","ba","bca","bda","bdca"] (already sorted by length)

wordpredecessors trieddp value
a(none, len 1)1
b(none, len 1)1
ba"a"(exist,1), "b"(exist,1)max(1+1,1+1)=2
bca"ca", "ba"(exist,2), "bc"max(dp["ba"]+1)=3
bda"da", "ba"(exist,2), "bd"max(dp["ba"]+1)=3
bdca"dca","bca"(exist,3),"bda"(exist,3),"bdc"max(3+1,3+1)=4

best = 4 ✓ Chain: a→ba→bda→bdca

Edge Cases​

  • Single word → 1
  • No predecessors → all dp values = 1, return 1
  • All words form one long chain → return n

Complexity​

  • Time: O(n × L²) — for each of n words, try L removals, each O(L) for slicing
  • Space: O(n × L) for dp map

Key Terms​

TermDefinition
Dynamic Programming (DP)Building the answer to a large problem from cached answers to smaller subproblems, here dp[word] = longest chain ending at word.
PredecessorA word that becomes the current word after inserting exactly one character.
Sort by lengthPreprocessing step ensuring every possible predecessor is already processed (and in dp) before the current word is evaluated.
Hashing (dict lookup)Using a hash map (dp) for O(1) average lookup of whether a candidate predecessor was already seen.

FAQ​

Q: Can this be solved without extra space? A: No — the dp dictionary is essential to avoid recomputation; without memoization the approach degrades into exponential re-derivation of chains.

Q: What if the input array is empty or has one word? A: An empty list returns best = 1 by default in most implementations (though the loop never runs, so guard for that); a single word returns 1, since dp[word] = 1 and no predecessors exist.

Q: Why must words be sorted by length before the main loop? A: Because dp[prev] must already be computed when we look it up — sorting guarantees every shorter word is processed before any longer word that could depend on it.

Q: How would this change if insertion could add more than one character? A: The predecessor generation (word[:i] + word[i+1:]) would need to remove multiple characters in combination, which is far more expensive — this problem's O(L) removal-per-position trick specifically relies on "exactly one" character difference.

Q: Iterative DP vs top-down memoized recursion — which is preferable here? A: Iterative (as shown) is simpler because sorting by length naturally establishes the correct processing order; a recursive version would need explicit memoization but avoids needing to pre-sort.

Quick Revision​

  • Goal: find the longest chain where each word is formed by inserting one letter into the previous word.
  • Sort words by length so every possible predecessor is processed before its successors.
  • For each word, try removing one character at each index to generate a candidate predecessor string.
  • If a candidate exists in dp, dp[word] = max(dp[word], dp[candidate] + 1).
  • Track the running maximum (best) across all words.
  • Time: O(n × L²) — n words, L removal candidates, each O(L) to build via slicing.
  • Space: O(n × L) for storing all words as dict keys.
  • This is a variant of Longest Increasing Subsequence where "increasing" means "one insertion away" instead of "numerically greater."
  • 300 - Longest Increasing Subsequence — same "chain-building DP over sorted input" pattern.
  • Word Ladder / Word Ladder II (pattern: BFS over one-character-edit graphs) — not in this directory.
  • Longest Common Subsequence (pattern: DP over string relationships) — not in this directory.