Skip to main content

1048. Longest String Chain

medium

Sort words by length; each word's chain length = 1 + max chain length over its single-char-deletion predecessors. The 2D part: each word inspects (length, deletion-index) combinations to find predecessors.

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. Now any predecessor is processed before its successor.

Hint 2

For each word, try deleting each character to form a candidate predecessor; look up the candidate in a hash map of best-chain-length-by-word.

Hint 3

dp[word] = 1 + max over the up-to-len(word) deletion variants that exist as keys in the map.

Hint 4

Answer is the global max across all words. Time O(N * L^2) for L = max word length.

Solution approach

Reveal approach

Sort words by length ascending so any predecessor has been processed before its successor. Maintain a hash map dp from word to the length of the longest chain ending at that word. For each word in sorted order, set dp[word] = 1 (a chain of just itself). Then for each index i in [0, len(word)), form the candidate predecessor by deleting word[i]. If the candidate exists in dp, update dp[word] = max(dp[word], dp[candidate] + 1). Track the global max. Time O(N * L^2) where L is max word length (deletion + hash insert at each cut). The 2D characterization comes from each word's inner sweep over the L deletion indices.

Complexity

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

Related patterns

  • dynamic-programming
  • string-dp
  • hash-map
  • sorting

Related problems

Asked at

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

  • Bloomberg
  • Goldman Sachs

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →