Longest String Chain solution and explanation
Google
9 more videos on this problem
DP 45. Longest String Chain | Longest Increasing Subsequence | LIStake U forward · 16:57 · 181K views
Longest String Chain | Same as LIS | FULL INTUITION | DP Concepts & Qns - 14 | Leetcode-1048codestorywithMIK · 29:53 · 23K views
Longest String Chain - Leetcode 1048 - PythonNeetCodeIO · 15:34 · 13K views
Longest String Chain | Live Coding with Explanation | Leetcode - 1048Algorithms Made Easy · 13:43 · 10K views
LeetCode 1048. Longest String Chain Explanation and Solutionhappygirlzt · 11:21 · 3K views
Leetcode 1048. Longest String ChainCode with Alisha · 14:33 · 3K views
Leetcode - Longest String Chain (Python)Timothy H Chang · 5:17 · 3K views
Longest String Chain | Leetcode 1048 | Live coding session | Google | FacebookCoding Decoded · 11:46 · 2K views
LeetCode 1048. Longest String ChainHappy Coding · 15:31 · 1K views
Longest String Chain | Leetcode 1048 | Dynamic ProgrammingAyushi Sharma · 22:03 · 1K views
The problem
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.
Approach overview
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 * L2) 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 * L2) 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.
Approach 1: Dynamic Programming with Sorting
This approach involves sorting the array of words based on their lengths, which helps in easily recognizing the potential predecessors. Then, utilize a dynamic programming technique to build up the solution. For each word, check all words that are predecessors and update the maximum chain length accordingly.
class Solution:
def longestStrChain(self, words):
words.sort(key=len)
dp = {}
max_len = 1
for word in words:
dp[word] = 1
for i in range(len(word)):
prev = word[:i] + word[i+1:]
if prev in dp:
dp[word] = max(dp[word], dp[prev] + 1)
max_len = max(max_len, dp[word])
return max_len
# Example usage:
solution = Solution()
words = ["a", "b", "ba", "bca", "bda", "bdca"]
print(solution.longestStrChain(words))import java.util.*;
public class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, Comparator.comparingInt(String::length));
Map<String, Integer> dp = new HashMap<>();
int maxLen = 1;
for (String word : words) {
dp.put(word, 1);
for (int i = 0; i < word.length(); i++) {
String prev = word.substring(0, i) + word.substring(i + 1);
if (dp.containsKey(prev)) {
dp.put(word, Math.max(dp.get(word), dp.get(prev) + 1));
}
}
maxLen = Math.max(maxLen, dp.get(word));
}
return maxLen;
}
public static void main(String[] args) {
Solution solution = new Solution();
String[] words = {"a", "b", "ba", "bca", "bda", "bdca"};
System.out.println(solution.longestStrChain(words));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
bool isPredecessor(const string &a, const string &b) {
if (b.length() != a.length() + 1) return false;
int i = 0, j = 0;
while (j < b.length()) {
if (i < a.length() && a[i] == b[j]) {
i++;
}
j++;
}
return i == a.length();
}
int longestStrChain(vector<string> &words) {
sort(words.begin(), words.end(), [](string &a, string &b) {
return a.length() < b.length();
});
unordered_map<string, int> dp;
int maxLen = 1;
for (const string &word : words) {
dp[word] = 1;
for (int i = 0; i < word.length(); i++) {
string prev = word.substr(0, i) + word.substr(i + 1);
if (dp.find(prev) != dp.end()) {
dp[word] = max(dp[word], dp[prev] + 1);
}
}
maxLen = max(maxLen, dp[word]);
}
return maxLen;
}
int main() {
vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
cout << longestStrChain(words) << endl;
return 0;
}var longestStrChain = function(words) {
words.sort((a, b) => a.length - b.length);
const dp = new Map();
let maxLen = 1;
for (const word of words) {
dp.set(word, 1);
for (let i = 0; i < word.length; i++) {
const prev = word.slice(0, i) + word.slice(i + 1);
if (dp.has(prev)) {
dp.set(word, Math.max(dp.get(word), dp.get(prev) + 1));
}
}
maxLen = Math.max(maxLen, dp.get(word));
}
return maxLen;
};
console.log(longestStrChain(["a", "b", "ba", "bca", "bda", "bdca"]));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
int cmp(const void *a, const void *b) {
return strlen(*(const char **)a) - strlen(*(const char **)b);
}
bool isPredecessor(char *a, char *b) {
if (strlen(b) != strlen(a) + 1) return false;
int i = 0, j = 0;
while (j < strlen(b)) {
if (i < strlen(a) && a[i] == b[j]) {
i++;
}
j++;
}
return i == strlen(a);
}
int longestStrChain(char **words, int wordsSize) {
int *dp = (int *)malloc(sizeof(int) * wordsSize);
memset(dp, 1, sizeof(int) * wordsSize);
qsort(words, wordsSize, sizeof(char *), cmp);
int maxLen = 1;
for (int i = 0; i < wordsSize; i++) {
for (int j = 0; j < i; j++) {
if (isPredecessor(words[j], words[i]) && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
if (maxLen < dp[i]) {
maxLen = dp[i];
}
}
free(dp);
return maxLen;
}
int main() {
char *words[] = {"a", "b", "ba", "bca", "bda", "bdca"};
int wordsSize = sizeof(words) / sizeof(words[0]);
printf("%d\n", longestStrChain(words, wordsSize));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int LongestStrChain(string[] words) {
Array.Sort(words, (a, b) => a.Length.CompareTo(b.Length));
Dictionary<string, int> dp = new Dictionary<string, int>();
int maxLen = 1;
foreach (string word in words) {
dp[word] = 1;
for (int i = 0; i < word.Length; i++) {
string prev = word.Substring(0, i) + word.Substring(i + 1);
if (dp.ContainsKey(prev)) {
dp[word] = Math.Max(dp[word], dp[prev] + 1);
}
}
maxLen = Math.Max(maxLen, dp[word]);
}
return maxLen;
}
public static void Main(string[] args) {
Solution solution = new Solution();
string[] words = new [] {"a", "b", "ba", "bca", "bda", "bdca"};
Console.WriteLine(solution.LongestStrChain(words));
}
}This Python solution uses a dictionary to store the longest chain length for each word. It sorts the list of words based on their lengths and iteratively finds the longest predecessor chain using substring checks.
Time Complexity: O(n * l^2), for similar reasons as the other implementations.
Space Complexity: O(n) for storing chain lengths in a dictionary.
Approach 2: Default Approach
function longestStrChain(words: string[]): number {
words.sort((a, b) => a.length - b.length);
let ans = 0;
let hashTable = new Map();
for (let word of words) {
let c = 1;
for (let i = 0; i < word.length; i++) {
let pre = word.substring(0, i) + word.substring(i + 1);
c = Math.max(c, (hashTable.get(pre) || 0) + 1);
}
hashTable.set(word, c);
ans = Math.max(ans, c);
}
return ans;
}func longestStrChain(words []string) int {
sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
res := 0
mp := make(map[string]int)
for _, word := range words {
x := 1
for i := 0; i < len(word); i++ {
pre := word[0:i] + word[i+1:len(word)]
x = max(x, mp[pre]+1)
}
mp[word] = x
res = max(res, x)
}
return res
}use std::collections::HashMap;
impl Solution {
#[allow(dead_code)]
pub fn longest_str_chain(words: Vec<String>) -> i32 {
let mut words = words;
let mut ret = 0;
let mut map: HashMap<String, i32> = HashMap::new();
// Sort the words vector first
words.sort_by(|lhs, rhs| lhs.len().cmp(&rhs.len()));
// Begin the "dp" process
for w in words.iter() {
let n = w.len();
let mut x = 1;
for i in 0..n {
let s = w[..i].to_string() + &w[i + 1..];
let v = map.entry(s.clone()).or_default();
x = std::cmp::max(x, *v + 1);
}
map.insert(w.clone(), x);
ret = std::cmp::max(ret, x);
}
ret
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | Time Complexity: O(n * l^2), for similar reasons as the other implementations. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Sorting | O(n log n + n * L²) | O(n) | Best general solution. Simple implementation and commonly expected in coding interviews. |
| Graph-Based (DAG + DFS/DP) | O(n * L²) | O(n + e) | Useful when modeling relationships between words or when you want to reconstruct the actual chain path. |
Frequently asked questions
Is Longest String Chain easy or hard?
Longest String Chain is generally classified as a medium difficulty problem. The implementation is straightforward once you recognize that shorter words must be processed first and that removing one character generates all possible predecessors.
How to solve Longest String Chain in O(n)?
A strict O(n) solution is not practical because each word must check multiple possible predecessors. The best practical approach is O(n log n + n * L^2) using dynamic programming and sorting. The extra cost comes from generating predecessor strings and sorting by length.
Longest String Chain Python or Java solution?
Python and Java solutions typically follow the same DP pattern: sort the words by length, store chain lengths in a hash map, and generate predecessors by removing one character. Each candidate predecessor is checked with constant-time map lookup to update the chain length.
What is the best approach for Longest String Chain?
Dynamic Programming with Sorting is the most efficient and widely used approach. Sort the words by length and compute the longest chain ending at each word using a hash map. For every word, generate predecessors by removing one character and check if they already exist. This produces an O(n log n + n * L^2) solution where L is the maximum word length.
What data structure is used in Longest String Chain?
The core data structure is a hash map that stores the longest chain length ending at each word. Sorting organizes words by length, while dynamic programming updates chain lengths. Some implementations also model the relationships as a graph or DAG.
What is the time complexity of Longest String Chain?
The optimal dynamic programming solution runs in O(n log n + n * L^2) time. Sorting the words takes O(n log n), and each word generates up to L predecessors, each costing O(L) to build. Space complexity is O(n) for storing the DP map of chain lengths.
Is Longest String Chain asked at Google, Amazon, or Meta?
Longest String Chain has appeared in interviews at large tech companies including Amazon, Google, and Meta because it tests dynamic programming on strings and hash-based lookups. It evaluates the ability to recognize predecessor relationships and build solutions incrementally.