Longest String Chain
Longest String Chain is a medium dynamic programming problem solved with the 1d dp pattern.
The best approach, optimal (hash map dp over deletions), runs in O(n log n + n · L²) time and O(n · L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (lis-style dp with pairwise checks) up.
Problem
You are given a list of words. Word a is a predecessor of word b when you can insert exactly one letter anywhere into a (without reordering the other letters) and get b.
A word chain is a sequence of words from the list where each word is a predecessor of the next one. A single word is a chain of length 1.
Return the length of the longest word chain you can build from the given words (each word may be used once per chain, in any order of the input).
Examples
Example 1
- Input
words = ["k", "ka", "kia", "kiwa", "zz"]- Output
4- Why
- "k" -> "ka" -> "kia" -> "kiwa": each step slips exactly one letter in somewhere.
Example 2
- Input
words = ["bed", "bead", "bread", "beard", "bearded"]- Output
3- Why
- "bed" -> "bead" -> "bread" (or "beard"). "bearded" is two letters longer than "beard", so it cannot extend the chain.
Example 3
- Input
words = ["cat", "dog"]- Output
1- Why
- No word can be built from another by adding one letter, so every chain is a single word.
Constraints
1 <= words.length <= 10001 <= words[i].length <= 16words[i]contains only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (LIS-style DP with pairwise checks) | O(n² · L) | O(n) |
| Optimal (hash map DP over deletions) | O(n log n + n · L²) | O(n · L) |
1Brute force (LIS-style DP with pairwise checks)
O(n² · L)Every pair of words is compared, and a comparison scans up to L characters.O(n)One dp value per word (plus the sort).Sort by length and treat it like longest increasing subsequence: dp[i] is the longest chain ending at word i, and for every earlier word j that is exactly one letter shorter we test with two pointers whether j is i with one letter removed.
- Sort the words by length.
- For each i, set dp[i] = 1, then for every j < i with len(j) + 1 == len(i), if isPred(j, i) then dp[i] = max(dp[i], dp[j] + 1).
- isPred walks both strings and allows exactly one skip in the longer one.
- Return the largest dp[i].
class Solution {
public int longestStrChain(String[] words) {
String[] w = words.clone();
Arrays.sort(w, (a, b) -> a.length() - b.length());
int n = w.length, best = 1;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++)
if (w[j].length() + 1 == w[i].length() && isPred(w[j], w[i]))
dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}
private boolean isPred(String a, String b) {
int i = 0, j = 0;
boolean skipped = false;
while (i < a.length() && j < b.length()) {
if (a.charAt(i) == b.charAt(j)) { i++; j++; }
else if (!skipped) { skipped = true; j++; }
else return false;
}
return true;
}
}class Solution:
def longestStrChain(self, words: List[str]) -> int:
w = sorted(words, key=len)
n = len(w)
dp = [1] * n
best = 1
for i in range(n):
for j in range(i):
if len(w[j]) + 1 == len(w[i]) and self.isPred(w[j], w[i]):
dp[i] = max(dp[i], dp[j] + 1)
best = max(best, dp[i])
return best
def isPred(self, a: str, b: str) -> bool:
i = j = 0
skipped = False
while i < len(a) and j < len(b):
if a[i] == b[j]:
i += 1
j += 1
elif not skipped:
skipped = True
j += 1
else:
return False
return Trueclass Solution {
public:
int longestStrChain(vector<string>& words) {
vector<string> w = words;
stable_sort(w.begin(), w.end(), [](const string& a, const string& b) { return a.size() < b.size(); });
int n = w.size(), best = 1;
vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (w[j].size() + 1 == w[i].size() && isPred(w[j], w[i]))
dp[i] = max(dp[i], dp[j] + 1);
best = max(best, dp[i]);
}
return best;
}
private:
bool isPred(const string& a, const string& b) {
size_t i = 0, j = 0;
bool skipped = false;
while (i < a.size() && j < b.size()) {
if (a[i] == b[j]) { i++; j++; }
else if (!skipped) { skipped = true; j++; }
else return false;
}
return true;
}
};function longestStrChain(words) {
const w = [...words].sort((a, b) => a.length - b.length);
const n = w.length;
const dp = new Array(n).fill(1);
let best = 1;
const isPred = (a, b) => {
let i = 0, j = 0, skipped = false;
while (i < a.length && j < b.length) {
if (a[i] === b[j]) { i++; j++; }
else if (!skipped) { skipped = true; j++; }
else return false;
}
return true;
};
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++)
if (w[j].length + 1 === w[i].length && isPred(w[j], w[i]))
dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}2Optimal (hash map DP over deletions)
O(n log n + n · L²)Each word produces L deletions, and building/hashing each costs O(L).O(n · L)The map stores every word as a key.Go from short words to long ones. Instead of comparing a word with every shorter word, generate its predecessors directly: delete each of its characters in turn and look the result up in a map of chain lengths already computed.
- Sort the words by length.
- For each word, best = 1; for every position k, pred = word without character k; if pred is in the map, best = max(best, map[pred] + 1).
- Store map[word] = max(map[word], best) and update the global answer.
class Solution {
public int longestStrChain(String[] words) {
String[] w = words.clone();
Arrays.sort(w, (a, b) -> a.length() - b.length());
Map<String, Integer> dp = new HashMap<>();
int ans = 0;
for (String word : w) {
int best = 1;
for (int k = 0; k < word.length(); k++) {
String pred = word.substring(0, k) + word.substring(k + 1);
Integer prev = dp.get(pred);
if (prev != null) best = Math.max(best, prev + 1);
}
dp.put(word, Math.max(dp.getOrDefault(word, 0), best));
ans = Math.max(ans, best);
}
return ans;
}
}class Solution:
def longestStrChain(self, words: List[str]) -> int:
dp = {}
ans = 0
for word in sorted(words, key=len):
best = 1
for k in range(len(word)):
pred = word[:k] + word[k + 1:]
if pred in dp:
best = max(best, dp[pred] + 1)
dp[word] = max(dp.get(word, 0), best)
ans = max(ans, best)
return ansclass Solution {
public:
int longestStrChain(vector<string>& words) {
vector<string> w = words;
stable_sort(w.begin(), w.end(), [](const string& a, const string& b) { return a.size() < b.size(); });
unordered_map<string, int> dp;
int ans = 0;
for (const string& word : w) {
int best = 1;
for (size_t k = 0; k < word.size(); k++) {
string pred = word.substr(0, k) + word.substr(k + 1);
auto it = dp.find(pred);
if (it != dp.end()) best = max(best, it->second + 1);
}
dp[word] = max(dp[word], best);
ans = max(ans, best);
}
return ans;
}
};function longestStrChain(words) {
const w = [...words].sort((a, b) => a.length - b.length);
const dp = new Map();
let ans = 0;
for (const word of w) {
let best = 1;
for (let k = 0; k < word.length; k++) {
const pred = word.slice(0, k) + word.slice(k + 1);
if (dp.has(pred)) best = Math.max(best, dp.get(pred) + 1);
}
dp.set(word, Math.max(dp.get(word) || 0, best));
ans = Math.max(ans, best);
}
return ans;
}Edge cases to test
- A single word (answer 1)
- Duplicate words in the input
- Words of equal length can never be neighbours in a chain
- Two words that differ by one letter in length but are not related by an insertion
Hints
Hint 1
If the words are processed from shortest to longest, every possible predecessor of a word has already been handled.
Hint 2
A word of length L has exactly L possible predecessors: delete one of its characters.
Hint 3
Store the best chain length ending at each word in a hash map keyed by the word itself.
FAQ
What is the best time complexity for Longest String Chain?
Optimal (hash map DP over deletions) runs in O(n log n + n · L²) time and O(n · L) extra space. Each word produces L deletions, and building/hashing each costs O(L).
Which pattern does Longest String Chain use?
It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).
Is there a brute force solution for Longest String Chain?
Yes. Brute force (LIS-style DP with pairwise checks) takes O(n² · L) time and O(n) space. Sort by length and treat it like longest increasing subsequence: dp[i] is the longest chain ending at word i, and for every earlier word j that is exactly one letter shorter we test with two pointers whether j is i with one letter removed.
Which edge cases should I test for Longest String Chain?
A single word (answer 1); Duplicate words in the input; Words of equal length can never be neighbours in a chain; Two words that differ by one letter in length but are not related by an insertion.