Longest String Chain
MedPrompt
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 <= 10001 <= words[i].length <= 16words[i]only consists of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the problem as finding the longest path in a graph. Each word is a node, and an edge exists from wordA to wordB if wordA is a predecessor of wordB. We perform a Depth First Search (DFS) from every single word to find the longest chain that can start with it. The overall maximum length found across all starting words is the answer. This method is highly inefficient because it recalculates the longest chain for the same words multiple times.
Algorithm
- Define a helper function
isPredecessor(wordA, wordB)that returns true ifwordAcan be transformed intowordBby adding a single character. - Define a recursive function
dfs(currentWord)that calculates the longest chain starting fromcurrentWord. - Inside
dfs(currentWord):- Initialize
maxLength = 1(for the word itself). - Iterate through every
nextWordin the global list of words. - If
isPredecessor(currentWord, nextWord)is true, it meansnextWordcan extend the chain. - Recursively call
dfs(nextWord)and update the length:maxLength = Math.max(maxLength, 1 + dfs(nextWord)). - Return
maxLength.
- Initialize
- The main function initializes a global maximum length to 0.
- It then iterates through every word in the input list, calling
dfsfor each one to treat it as a potential start of a chain. - The overall maximum length found is the answer.
Walkthrough
The algorithm works by exploring every possible chain exhaustively. The main function iterates through each word, treating it as a potential starting point. For each starting word, it calls a recursive DFS helper function, dfs(currentWord). This function calculates the length of the longest chain starting with currentWord by iterating through all other words to find valid successors. A word nextWord is a successor if currentWord is its predecessor. If a successor is found, the function recursively calls itself with the successor to explore that path further. The lack of memoization means that dfs(word) will be computed from scratch every time it's called, even if the result for that word has been found before in a different recursive branch, leading to exponential complexity.
class Solution { private String[] allWords; public int longestStrChain(String[] words) { this.allWords = words; int maxLen = 0; if (words == null || words.length == 0) return 0; for (String word : words) { maxLen = Math.max(maxLen, dfs(word)); } return maxLen; } private int dfs(String currentWord) { int maxLength = 1; for (String nextWord : this.allWords) { if (isPredecessor(currentWord, nextWord)) { maxLength = Math.max(maxLength, 1 + dfs(nextWord)); } } return maxLength; } private boolean isPredecessor(String wordA, String wordB) { if (wordA.length() + 1 != wordB.length()) { return false; } int i = 0; // pointer for wordA int j = 0; // pointer for wordB while (i < wordA.length() && j < wordB.length()) { if (wordA.charAt(i) == wordB.charAt(j)) { i++; } j++; } return i == wordA.length(); }}Complexity
Time
O(N! * L) or worse. This is a loose upper bound, but it reflects the exponential nature of the algorithm due to redundant computations. For each call, we iterate through N words, and the recursion depth can be up to N.
Space
O(N * L), where N is the number of words and L is the maximum word length. This is for the recursion stack in the worst case of a chain involving all N words.
Trade-offs
Pros
Conceptually simple and a direct translation of the problem definition.
Cons
Extremely inefficient due to massive re-computation of results for the same subproblems.
Will cause a 'Time Limit Exceeded' error on any non-trivial input size.
This approach significantly improves upon the brute-force DFS by using memoization (a form of caching) to avoid re-computing results for the same subproblems. We use a hash map to store the length of the longest chain starting from each word. When the DFS function is called for a word, it first checks if the result is already in the cache. If so, it returns the cached value immediately, effectively pruning the search space and preventing redundant calculations.
Algorithm
- Use a
Map<String, Integer> memoto store the computed results of the longest chain starting from a given word. - Use a
Set<String> wordSetfor fast lookups of words from the input array. - The main function iterates through all words, calling a recursive helper
dfs(word)for each. - The
dfs(currentWord)function is defined as follows:- Check if the result for
currentWordis already inmemo. If yes, return it. - Initialize
maxLength = 1. - Generate all potential successors of
currentWord. A successor is formed by inserting a character ('a' through 'z') at every possible position incurrentWord. - For each generated
successor, check if it exists inwordSet. - If it exists, recursively call
dfs(successor)and updatemaxLength = Math.max(maxLength, 1 + dfs(successor)). - Store the final
maxLengthinmemobefore returning.
- Check if the result for
Walkthrough
The algorithm is a memoized version of the DFS approach. A Map<String, Integer> memo stores the results of dfs(word), and a Set<String> wordSet provides fast word lookups. The main function calls dfs(word) for each word to ensure all possible chains are considered. The dfs(currentWord) function first checks the memoization table. If the result is not present, it calculates it by generating all possible successors (by inserting a character at each position), checking if they exist in the wordSet, and recursively calling dfs on them. The computed result is then stored in the memoization table to be reused later.
import java.util.*; class Solution { public int longestStrChain(String[] words) { Set<String> wordSet = new HashSet<>(Arrays.asList(words)); Map<String, Integer> memo = new HashMap<>(); int maxLen = 0; for (String word : words) { maxLen = Math.max(maxLen, dfs(word, wordSet, memo)); } return maxLen; } private int dfs(String currentWord, Set<String> wordSet, Map<String, Integer> memo) { if (memo.containsKey(currentWord)) { return memo.get(currentWord); } int maxLength = 1; // Generate potential successors and check if they exist for (int i = 0; i <= currentWord.length(); i++) { for (char c = 'a'; c <= 'z'; c++) { String successor = new StringBuilder(currentWord).insert(i, c).toString(); if (wordSet.contains(successor)) { maxLength = Math.max(maxLength, 1 + dfs(successor, wordSet, memo)); } } } memo.put(currentWord, maxLength); return maxLength; }}Complexity
Time
O(N * L^2). For each of the N words, we compute its result once. The computation involves a loop of size L (for insertion position), and inside it, string building (O(L)) and hash set lookup (O(L) due to string hashing). This gives a complexity of O(L^2) for each of the N states.
Space
O(N * L), where N is the number of words and L is the max word length. This space is used for the memoization map and the recursion stack.
Trade-offs
Pros
Much faster than brute-force by eliminating redundant computations.
Guarantees that the subproblem for each word is solved only once.
Cons
The time complexity, while polynomial, can still be slow for the given constraints.
Deep recursion could lead to a stack overflow error if a very long chain exists.
This is the most efficient approach, utilizing bottom-up dynamic programming. It builds the solution iteratively by processing words from shortest to longest. By sorting the words by length, we ensure that when we calculate the longest chain for any given word, we have already computed the results for all of its potential, shorter predecessors. This avoids recursion and builds the solution from the ground up.
Algorithm
- Sort the
wordsarray based on the length of the strings in ascending order. - Create a hash map
dpwheredp[word]will store the length of the longest chain ending with thatword. - Initialize a variable
maxChainLength = 0. - Iterate through each
wordin the sorted array:- Initialize
currentLongest = 1for the chain consisting of theworditself. - Generate all possible predecessors of the current
wordby deleting one character at each position. - For each generated
predecessor, look up its longest chain length in thedpmap:prevLength = dp.getOrDefault(predecessor, 0). - Update the longest chain for the current word:
currentLongest = Math.max(currentLongest, prevLength + 1). - Store this result in the map:
dp.put(word, currentLongest). - Update the overall
maxChainLength = Math.max(maxChainLength, currentLongest).
- Initialize
- Return
maxChainLengthafter the loop.
Walkthrough
The algorithm begins by sorting the input words array by length. This is the key step that allows for a bottom-up approach. We use a hash map, dp, to store the length of the longest chain ending at each word. We iterate through the sorted words. For each word, we try to form a chain by finding a predecessor. A predecessor is one character shorter, so we generate all possible predecessors by deleting one character from the current word. Since the words are sorted by length, the dp value for any valid predecessor will have already been computed. We look up the predecessor's chain length in the dp map, add 1 (for the current word), and update the dp value for the current word with the maximum length found. The overall maximum is tracked and returned.
import java.util.*; class Solution { public int longestStrChain(String[] words) { Arrays.sort(words, (a, b) -> a.length() - b.length()); Map<String, Integer> dp = new HashMap<>(); int maxChainLength = 0; for (String word : words) { int currentLongest = 1; for (int i = 0; i < word.length(); i++) { StringBuilder sb = new StringBuilder(word); String predecessor = sb.deleteCharAt(i).toString(); int prevLength = dp.getOrDefault(predecessor, 0); currentLongest = Math.max(currentLongest, prevLength + 1); } dp.put(word, currentLongest); maxChainLength = Math.max(maxChainLength, currentLongest); } return maxChainLength; }}Complexity
Time
O(N log N + N * L^2). The `O(N log N)` term comes from sorting the array. The main loop runs `N` times. Inside, we iterate `L` times to generate predecessors. String manipulation (e.g., `StringBuilder.deleteCharAt`) and hash map operations with string keys take `O(L)` time. This results in the `O(N * L^2)` term.
Space
O(N * L), where N is the number of words and L is the maximum word length, to store the `dp` map.
Trade-offs
Pros
Most efficient time complexity among the approaches.
Iterative solution avoids recursion and the risk of stack overflow.
The logic is clean and directly builds towards the solution.
Cons
Requires an initial sorting step, which adds an O(N log N) factor to the complexity.
The space complexity is proportional to the number and length of words.
Solutions
Solution
class Solution {public int longestStrChain(String[] words) { Arrays.sort(words, Comparator.comparingInt(String : : length)); int res = 0; Map<String, Integer> map = new HashMap<>(); for (String word : words) { int x = 1; for (int i = 0; i < word.length(); ++i) { String pre = word.substring(0, i) + word.substring(i + 1); x = Math.max(x, map.getOrDefault(pre, 0) + 1); } map.put(word, x); res = Math.max(res, x); } return res; }}class Solution { public: int longestStrChain ( vector < string >& words ) { sort ( words . begin (), words . end (), [ & ]( string a , string b ) { return a . size () < b . size (); }); int res = 0 ; unordered_map < string , int > map ; for ( auto word : words ) { int x = 1 ; for ( int i = 0 ; i < word . size (); ++ i ) { string pre = word . substr ( 0 , i ) + word . substr ( i + 1 ); x = max ( x , map [ pre ] + 1 ); } map [ word ] = x ; res = max ( res , x ); } return res ; } };class Solution: def longestStrChain(self, words: List[str]) -> int: def check(w1, w2): if len(w2) - len(w1) != 1: return False i = j = cnt = 0 while i < len(w1) and j < len(w2): if w1[i] != w2[j]: cnt += 1 else: i += 1 j += 1 return cnt < 2 and i == len(w1) n = len(words) dp = [1] * (n + 1) words . sort(key=lambda x: len(x)) res = 1 for i in range(1, n): for j in range(i): if check(words[j], words[i]): dp[i] = max(dp[i], dp[j] + 1) res = max(res, dp[i]) return resVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.