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.
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; }}Video 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.