Skip to main content
Talentd

Longest String Chain - Solution & Explanation

MediumArrayHash TableTwo PointersString17 min readAsked at: Amazon, Microsoft, Meta +13
Practice this problem

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 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.

 

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","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
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

 

Constraints:

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

Approach Overview

Problem Overview: You are given a list of words. A word A is a predecessor of word B if you can insert exactly one character anywhere in A to form B. The task is to compute the maximum length of a chain where each word is formed from the previous one by adding a single character.

Approach 1: Dynamic Programming with Sorting (O(n log n + n * L2) time, O(n) space)

The key observation: a valid predecessor must be exactly one character shorter than the current word. Start by sorting all words by length using sorting. This guarantees that when processing a word, all possible predecessors were already processed. Maintain a hash map where dp[word] stores the longest chain ending at that word.

For each word, generate all possible predecessors by removing one character at every index. Example: from "abcd" generate "bcd", "acd", "abd", "abc". Check each candidate with a constant-time lookup in a hash table. If the predecessor exists, update the chain length: dp[word] = max(dp[word], dp[pred] + 1). Track the global maximum while iterating.

This approach works well because each word only checks L possible predecessors, and each predecessor creation costs O(L). Combined with the initial sort, the overall complexity becomes O(n log n + n * L2), where L is the maximum word length. This solution is concise and commonly expected in interviews using dynamic programming.

Approach 2: Graph-Based Approach (O(n * L2) time, O(n + e) space)

You can also model the problem as a directed graph. Each word is a node, and an edge exists from word a to b if a is a predecessor of b. Since every step increases word length by exactly one, the graph is naturally a Directed Acyclic Graph (DAG).

Build adjacency relationships by checking whether removing one character from a longer word produces a shorter word in the set. After constructing the graph, run DFS with memoization or dynamic programming on the DAG to compute the longest path starting from each node. Cache results so each node is processed once.

This method reaches similar complexity to the DP approach because predecessor checks still require generating L candidate strings per word. It is useful if you want to explicitly visualize the chain relationships or extend the problem to recover the actual sequence of words.

Recommended for interviews: Dynamic Programming with Sorting is the solution interviewers typically expect. Sorting ensures valid build order, and the predecessor generation trick shows strong understanding of string manipulation and DP state transitions. Explaining the brute reasoning first (checking shorter predecessors) and then optimizing with a hash map demonstrates good problem-solving progression.

Approach 1: Dynamic Programming with Sorting

This approach involves sorting the array of words based on their lengths, which helps in easily recognizing the potential predecessors. Then, utilize a dynamic programming technique to build up the solution. For each word, check all words that are predecessors and update the maximum chain length accordingly.

The solution is implemented in C using dynamic programming. First, it sorts the array of words according to their lengths. Then, for each word, it checks all previously encountered words to see if they can form a predecessor-successor pair. The dynamic programming array (dp) keeps track of the maximum chain length for each word. The final result is the maximum value in this array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * l), where n is the number of words and l is the average length of each word. The sorting step contributes O(n log n) but checking each predecessor might happen in O(n^2). The maximum comparison takes O(l) time.
Space Complexity: O(n) for the dp array.

Try this approach in the editor ā†’

Approach 2: Graph-Based Approach

This approach models the words as nodes in a graph and links words via edges if one is a predecessor of the other. The goal is to find the longest path in this directed acyclic graph (DAG), which represents the longest word chain.

This C solution approaches the problem by leveraging the concept of words as nodes in a directed graph. It calculates the longest path in this graph by identifying predecessors.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * l), where n is the number of words and l is the average word length as this is similar to a dynamic programming solution.
Space Complexity: O(n) for the dynamic programming path length array.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Dynamic Programming with Sorting

Time Complexity: O(n^2 * l), where n is the number of words and l is the average length of each word. The sorting step contributes O(n log n) but checking each predecessor might happen in O(n^2). The maximum comparison takes O(l) time.
Space Complexity: O(n) for the dp array.

Graph-Based Approach

Time Complexity: O(n^2 * l), where n is the number of words and l is the average word length as this is similar to a dynamic programming solution.
Space Complexity: O(n) for the dynamic programming path length array.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with SortingO(n log n + n * LĀ²)O(n)Best general solution. Simple implementation and commonly expected in coding interviews.
Graph-Based (DAG + DFS/DP)O(n * LĀ²)O(n + e)Useful when modeling relationships between words or when you want to reconstruct the actual chain path.

Video Solution

DP 45. Longest String Chain | Longest Increasing Subsequence | LIS ā€¢ take U forward ā€¢ 181,731 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Longest String Chain easy or hard?
Longest String Chain is generally classified as a medium difficulty problem. The implementation is straightforward once you recognize that shorter words must be processed first and that removing one character generates all possible predecessors.
How to solve Longest String Chain in O(n)?
A strict O(n) solution is not practical because each word must check multiple possible predecessors. The best practical approach is O(n log n + n * L^2) using dynamic programming and sorting. The extra cost comes from generating predecessor strings and sorting by length.
Longest String Chain Python or Java solution?
Python and Java solutions typically follow the same DP pattern: sort the words by length, store chain lengths in a hash map, and generate predecessors by removing one character. Each candidate predecessor is checked with constant-time map lookup to update the chain length.
What is the best approach for Longest String Chain?
Dynamic Programming with Sorting is the most efficient and widely used approach. Sort the words by length and compute the longest chain ending at each word using a hash map. For every word, generate predecessors by removing one character and check if they already exist. This produces an O(n log n + n * L^2) solution where L is the maximum word length.
What data structure is used in Longest String Chain?
The core data structure is a hash map that stores the longest chain length ending at each word. Sorting organizes words by length, while dynamic programming updates chain lengths. Some implementations also model the relationships as a graph or DAG.
What is the time complexity of Longest String Chain?
The optimal dynamic programming solution runs in O(n log n + n * L^2) time. Sorting the words takes O(n log n), and each word generates up to L predecessors, each costing O(L) to build. Space complexity is O(n) for storing the DP map of chain lengths.
Is Longest String Chain asked at Google, Amazon, or Meta?
Longest String Chain has appeared in interviews at large tech companies including Amazon, Google, and Meta because it tests dynamic programming on strings and hash-based lookups. It evaluates the ability to recognize predecessor relationships and build solutions incrementally.

Ready to solve this problem?

Practice Longest String Chain with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays