Log inSign up
mediumLeetCodeNot Started

Longest String Chain

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

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 [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

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 words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

### Example 3 - Input: words = ["abcd", "dbqca"] - Output: 1

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply LIS dynamic programming to string transformations.
  • Generate predecessor strings via single-character deletions.
  • Leverage small string length constraints (L <= 16) for efficient hashing.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Chain of words where each step adds exactly 1 character.
  • Maximizing chain length.

Algorithmic Decision Tree:

  • Sort by word length first.
  • Use hash map for O(1) predecessor lookup.

Connected Patterns:

Longest Increasing SubsequenceWord LadderRussian Doll Envelopes

1. Recursive Predecessor DFS

Intuition

Recursively search all valid predecessors for each word from the input set.

Algorithm

  1. Store words in a hash set for quick membership checking.
  2. Define dfs(word): returns max chain ending at word.
  3. For each character in word:
  4. Create prev by removing that character.
  5. If prev in set, maxChain = max(maxChain, 1 + dfs(prev)).
  6. Return maxChain.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <algorithm>
6
7using namespace std;
8
9class Solution {
10 int dfs(const string& word, const unordered_set<string>& wordSet) {
11 int maxChain = 1;
12 for (int i = 0; i < word.length(); ++i) {
13 string prev = word.substr(0, i) + word.substr(i + 1);
14 if (wordSet.count(prev)) {
15 maxChain = max(maxChain, 1 + dfs(prev, wordSet));
16 }
17 }
18 return maxChain;
19 }
20public:
21 int longestStrChain(vector<string>& words) {
22 unordered_set<string> wordSet(words.begin(), words.end());
23 int ans = 1;
24 for (const string& w : words) {
25 ans = max(ans, dfs(w, wordSet));
26 }
27 return ans;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
34 cout << "Longest Chain: " << sol.longestStrChain(words) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(L^n)
  • Space complexity: O(n) call stack

2. Memoized DFS with Hash Map

Intuition

Store memoized longest chain values for each word in a hash map.

Algorithm

  1. Initialize hash map memo.
  2. In dfs(word): return memo[word] if already computed.
  3. Compute max chain over all 1-character deletions.
  4. Store and return memo[word].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <unordered_map>
6#include <algorithm>
7
8using namespace std;
9
10class Solution {
11 int dfs(const string& word, const unordered_set<string>& wordSet, unordered_map<string, int>& memo) {
12 if (memo.count(word)) return memo[word];
13
14 int maxChain = 1;
15 for (int i = 0; i < word.length(); ++i) {
16 string prev = word.substr(0, i) + word.substr(i + 1);
17 if (wordSet.count(prev)) {
18 maxChain = max(maxChain, 1 + dfs(prev, wordSet, memo));
19 }
20 }
21
22 return memo[word] = maxChain;
23 }
24public:
25 int longestStrChain(vector<string>& words) {
26 unordered_set<string> wordSet(words.begin(), words.end());
27 unordered_map<string, int> memo;
28 int ans = 1;
29 for (const string& w : words) {
30 ans = max(ans, dfs(w, wordSet, memo));
31 }
32 return ans;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
39 cout << "Longest Chain: " << sol.longestStrChain(words) << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(n * L^2)
  • Space complexity: O(n * L)

3. Sort by Length + Hash Map Tabulation (Bottom-Up)

Intuition

Sort words by length in ascending order. Maintain a hash map dp[word]. For each word, look up all 1-character deletions in O(1).

Algorithm

  1. Sort words by length in ascending order.
  2. Initialize hash map dp.
  3. Track maxChain = 1.
  4. For each word in words:
  5. dp[word] = 1.
  6. For each index i from 0 to word.length - 1:
  7. prev = word.substr(0, i) + word.substr(i + 1).
  8. If prev in dp:
  9. dp[word] = max(dp[word], 1 + dp[prev]).
  10. maxChain = max(maxChain, dp[word]).
  11. Return maxChain.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <algorithm>
6
7using namespace std;
8
9class Solution {
10public:
11 int longestStrChain(vector<string>& words) {
12 sort(words.begin(), words.end(), [](const string& a, const string& b) {
13 return a.length() < b.length();
14 });
15
16 unordered_map<string, int> dp;
17 int maxChain = 1;
18
19 for (const string& word : words) {
20 dp[word] = 1;
21 for (int i = 0; i < word.length(); ++i) {
22 string prev = word.substr(0, i) + word.substr(i + 1);
23 if (dp.count(prev)) {
24 dp[word] = max(dp[word], 1 + dp[prev]);
25 }
26 }
27 maxChain = max(maxChain, dp[word]);
28 }
29
30 return maxChain;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
37 cout << "Longest Chain: " << sol.longestStrChain(words) << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(n log n + n * L^2)
  • Space complexity: O(n * L)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Predecessor DFSO(L^n)O(n)Exhaustive branching over single character deletions.Subtree overlap
2.Memoized DFSO(n * L^2)O(n * L)Memoize longest chain for each word.Call stack
3.Sort by Length + Hash Map DPOptimalO(n log n + n * L^2)O(n * L)Sort by length and tabulate forward with hash map.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Sorting alphabetically rather than by word length: Prevents topological ordering required for DP.

Pitfall 2:

Comparing all pairs of words in O(n2 * L) instead of generating L deletions in O(n * L2) (since n <= 1000 and L <= 16, L2 is 256 while n is 1000).

Crucial Edge Cases to Validate:

  • Single word: Returns 1.
  • No two words can form a chain: Returns 1.
  • Duplicate words of the same length: Handled correctly by sorting and map lookup.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why deleting from the longer word (L deletions) is faster than adding 26 letters at every position of the shorter word (26 * L possibilities).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it sufficient to check only the L single-character deletions of a word to find predecessors?

Back to DSA Sheet