Longest String Chain - Solution & Explanation

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 * L²) 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 * L²) 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.