Skip to main content

1048. Longest String Chain

medium

Find the longest chain of words where each predecessor adds one letter to form the next. Sort by length, then DP keyed on the string itself.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 1

Input
words = ["a","b","ba","bca","bda","bdca"]
Output
4

Explanation: One of the longest word chains is ["a","ba","bca","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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort words by length ascending. Predecessors are always shorter, so chains build forward.

Hint 2

Hash map dp[word] = length of the longest chain ending at word.

Hint 3

For each word, for each position i remove the i-th char and look up the result in dp. dp[word] = max(dp[word], dp[predecessor] + 1).

Solution approach

Reveal approach

Sort words by length ascending — predecessors are always strictly shorter than successors, so processing in length order means predecessors are already resolved. Maintain a hash map dp where dp[w] is the length of the longest chain ending at word w. For each word w, initialize dp[w] = 1. For each position i in w, form the candidate predecessor by removing the character at index i (one allocation per check). If that predecessor is in dp, update dp[w] = max(dp[w], dp[predecessor] + 1). Track the global max. O(N * L^2) time where L is the maximum word length — L positions, each forming a length-(L-1) substring.

Complexity

Time
O(N * L^2)
Space
O(N)

Related patterns

  • dynamic-programming
  • hash-map
  • sorting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Longest String Chain and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →