Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest String Chain

MEDIUMProblemSolveExternal Links

Description

You are given an array of words where each word consists of lowercase English letters.

A word wordA is called a predecessor of another word wordB if and only if you 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" because inserting 'a' at position 2 in "abc" produces "abac". However, "cba" is not a predecessor of "bcad" because the character order would need to change.

A word chain is a sequence of words [word₁, word₂, ..., wordₖ] where k ≥ 1, and each wordᵢ is a predecessor of wordᵢ₊₁. A single word by itself is trivially a word chain of length 1.

Return the length of the longest possible word chain that can be formed using words chosen from the given list.

Examples

Example 1

Input: words = ["a", "b", "ba", "bca", "bda", "bdca"]

Output: 4

Explanation: One of the longest word chains is ["a", "ba", "bda", "bdca"]. Each word is formed by inserting exactly one letter into its predecessor:

  • "a" → insert 'b' at position 0 → "ba"
  • "ba" → insert 'd' at position 1 → "bda"
  • "bda" → insert 'c' at position 2 → "bdca"

Another valid chain of the same length is ["a", "ba", "bca", "bdca"]. The maximum chain length is 4.

Example 2

Input: words = ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]

Output: 5

Explanation: All five words can form a single chain: ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"]. Each word is a predecessor of the next:

  • "xb" → insert 'c' → "xbc"
  • "xbc" → insert 'c' at front → "cxbc"
  • "cxbc" → insert 'p' at front → "pcxbc"
  • "pcxbc" → insert 'f' at end → "pcxbcf"

The entire array forms a chain of length 5.

Example 3

Input: words = ["abcd", "dbqca"]

Output: 1

Explanation: Neither word can be a predecessor of the other. Although "abcd" (length 4) is one character shorter than "dbqca" (length 5), inserting any single letter into "abcd" cannot produce "dbqca" without reordering the characters. The longest chain is a single word by itself, giving a length of 1.

Constraints

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

Editorial

Brute Force

Intuition

The most natural starting point is to think about building word chains by exploration. Imagine you have all the words spread out on a table. You pick up one word, then look for any word that is exactly one character longer and can be formed by inserting a letter into your current word. When you find such a word, you continue the chain from there, exploring all possible extensions.

This is essentially a graph-exploration problem. Each word is a node, and there is a directed edge from word A to word B if A is a predecessor of B (i.e., you can insert one character into A to get B). We want the longest path in this directed graph.

The brute-force strategy is to try starting a chain from every word in the list. For each starting word, we use recursion (DFS) to explore all possible successor words and track the longest chain we can build. We do not store any intermediate results — every time we reach the same word through a different path, we recompute its best chain length from scratch.

To check whether word A is a predecessor of word B, we verify two things: B must be exactly one character longer than A, and we must be able to match all characters of A in order within B, skipping exactly one character in B.

Step-by-Step Explanation

Let's trace through with words = ["a", "b", "ba", "bca", "bda", "bdca"].

First, sort by length: ["a", "b", "ba", "bca", "bda", "bdca"].

Step 1: Start DFS from "a" (length 1). Look for successors of length 2.

Step 2: Found "ba" — is "a" a predecessor of "ba"? Remove characters from "ba" one at a time: remove 'b' → "a" matches. Yes! Recurse into dfs("ba").

Step 3: From "ba" (length 2), look for successors of length 3. Found "bca" — remove 'c' from "bca" → "ba". Predecessor confirmed. Recurse into dfs("bca").

Step 4: From "bca" (length 3), look for successors of length 4. Found "bdca" — remove 'd' from "bdca" → "bca". Predecessor confirmed. Recurse into dfs("bdca").

Step 5: From "bdca" (length 4), no words of length 5 exist. Return chain length = 1.

Step 6: Back to "bca": best successor chain = 1. Chain from "bca" = 1 + 1 = 2.

Step 7: Back to "ba": also check "bda" — remove 'd' from "bda" → "ba". Predecessor confirmed. Recurse into dfs("bda").

Step 8: From "bda", find successor "bdca" — remove 'c' from "bdca" → "bda". Recurse into dfs("bdca"). Notice: we are computing dfs("bdca") a second time because we have no memoization!

Step 9: dfs("bdca") returns 1 again (recomputed). dfs("bda") = 1 + 1 = 2.

Step 10: Back to "ba": max(dfs("bca"), dfs("bda")) = max(2, 2) = 2. Chain from "ba" = 1 + 2 = 3.

Step 11: Back to "a": chain from "a" = 1 + 3 = 4.

Result: After trying all starting words, the longest chain = 4.

Brute Force — Recursive Chain Exploration from "a" — Watch how DFS explores all possible chain extensions starting from word "a", recomputing dfs("bdca") twice because there is no memoization.

Algorithm

  1. Sort the words array by word length (ascending)
  2. Define a helper function isPredecessor(a, b) that checks whether word a can become word b by inserting exactly one character
  3. Define dfs(idx) that returns the longest chain starting from words[idx]:
    • Initialize best = 1 (the word itself)
    • For every word j after idx where isPredecessor(words[idx], words[j]) is true:
      • Recursively compute dfs(j) and update best = max(best, 1 + dfs(j))
    • Return best
  4. Call dfs(i) for every word index i and return the maximum result

Code

class Solution {
public:
    bool isPredecessor(const string& a, const string& b) {
        if (a.size() + 1 != b.size()) return false;
        int i = 0;
        for (int j = 0; j < b.size(); j++) {
            if (i < a.size() && a[i] == b[j]) i++;
        }
        return i == (int)a.size();
    }

    int dfs(int idx, vector<string>& words) {
        int best = 1;
        for (int j = idx + 1; j < words.size(); j++) {
            if (isPredecessor(words[idx], words[j])) {
                best = max(best, 1 + dfs(j, words));
            }
        }
        return best;
    }

    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });
        int result = 1;
        for (int i = 0; i < words.size(); i++) {
            result = max(result, dfs(i, words));
        }
        return result;
    }
};
class Solution:
    def longestStrChain(self, words: list[str]) -> int:
        words.sort(key=len)

        def is_predecessor(a: str, b: str) -> bool:
            if len(a) + 1 != len(b):
                return False
            i = 0
            for ch in b:
                if i < len(a) and a[i] == ch:
                    i += 1
            return i == len(a)

        def dfs(idx: int) -> int:
            best = 1
            for j in range(idx + 1, len(words)):
                if is_predecessor(words[idx], words[j]):
                    best = max(best, 1 + dfs(j))
            return best

        result = 1
        for i in range(len(words)):
            result = max(result, dfs(i))
        return result
class Solution {
    private boolean isPredecessor(String a, String b) {
        if (a.length() + 1 != b.length()) return false;
        int i = 0;
        for (int j = 0; j < b.length(); j++) {
            if (i < a.length() && a.charAt(i) == b.charAt(j)) i++;
        }
        return i == a.length();
    }

    private int dfs(int idx, String[] words) {
        int best = 1;
        for (int j = idx + 1; j < words.length; j++) {
            if (isPredecessor(words[idx], words[j])) {
                best = Math.max(best, 1 + dfs(j, words));
            }
        }
        return best;
    }

    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        int result = 1;
        for (int i = 0; i < words.length; i++) {
            result = Math.max(result, dfs(i, words));
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(2^n × L)

In the worst case, the recursion tree branches at every word, leading to an exponential number of recursive calls. Each call involves checking the predecessor relationship, which takes O(L) time where L is the maximum word length. Without memoization, the same subproblems are recomputed many times, making the total time exponential in the number of words.

Space Complexity: O(n)

The recursion stack can go as deep as n (the number of words) in the worst case, where every word forms a chain. Sorting requires O(log n) additional space. Total auxiliary space is O(n).

Why This Approach Is Not Efficient

The brute-force recursion has exponential time complexity because it recomputes the same subproblems over and over. In our trace, dfs("bdca") was called twice — once from the bca branch and once from the bda branch — both returning the same answer.

With n up to 1000 words, the exponential blowup makes this approach completely impractical. Even for moderate inputs (n = 20-30), the recursion tree grows to millions of calls.

The key insight is that this problem has overlapping subproblems: the longest chain starting (or ending) at a particular word is always the same, regardless of how we reached that word. This is exactly the property that Dynamic Programming exploits. Instead of recomputing from scratch every time, we can store each word's chain length once and reuse it.

Better Approach - LIS-Style Dynamic Programming

Intuition

This problem is structurally similar to the classic Longest Increasing Subsequence (LIS) problem. In LIS, you sort numbers and for each element, you look back at all smaller elements to find the longest chain ending there. Here, instead of comparing numeric values, we compare word lengths and check the predecessor relationship.

The idea is:

  1. Sort all words by length. This ensures that any potential predecessor of a word appears before it in the sorted order.
  2. Create a dp array where dp[i] represents the longest chain ending at words[i].
  3. For each word i, examine every previous word j. If words[j] is a predecessor of words[i], then we can extend the chain ending at j by one more word, giving us dp[i] = max(dp[i], dp[j] + 1).

This guarantees we consider every possible chain because we process words in order of increasing length, and for each word we check all possible predecessors.

Step-by-Step Explanation

Let's trace with words = ["a", "b", "ba", "bca", "bda", "bdca"] (already sorted by length).

Initialize dp = [1, 1, 1, 1, 1, 1] (each word alone is a chain of length 1).

Step 1: i=0 ("a"). No words before it. dp[0] = 1.

Step 2: i=1 ("b"). Check j=0 ("a"): len("a")=1, len("b")=1. Same length — cannot be a predecessor (need length difference of 1). dp[1] = 1.

Step 3: i=2 ("ba"). Check j=0 ("a"): len("a")=1, len("ba")=2, diff=1. Is "a" predecessor of "ba"? Remove 'b' from "ba" → "a" = "a". Yes! dp[2] = dp[0] + 1 = 2.

Step 4: i=2, j=1 ("b"): len diff=1. Is "b" predecessor of "ba"? Remove 'a' from "ba" → "b" = "b". Yes! dp[2] = max(2, dp[1]+1) = max(2, 2) = 2.

Step 5: i=3 ("bca"). Check j=2 ("ba"): len diff=1. Is "ba" predecessor of "bca"? Remove 'c' → "ba" = "ba". Yes! dp[3] = dp[2] + 1 = 3.

Step 6: i=4 ("bda"). Check j=2 ("ba"): len diff=1. Remove 'd' from "bda" → "ba". Yes! dp[4] = dp[2] + 1 = 3.

Step 7: i=5 ("bdca"). Check j=3 ("bca"): len diff=1. Remove 'd' from "bdca" → "bca". Yes! dp[5] = dp[3] + 1 = 4.

Step 8: i=5, j=4 ("bda"): len diff=1. Remove 'c' from "bdca" → "bda". Yes! dp[5] = max(4, dp[4]+1) = max(4, 4) = 4.

Result: max(dp) = 4. The dp array is [1, 1, 2, 3, 3, 4].

LIS-Style DP — Building Longest Chains Bottom-Up — Watch how we fill the dp array by checking all previous words for predecessor relationships, building up chain lengths from shorter to longer words.

Algorithm

  1. Sort words by length (ascending)
  2. Create a dp array of size n, initialized to 1 (every word is a chain of length 1)
  3. For each word index i from 1 to n-1:
    • For each previous index j from 0 to i-1:
      • If words[j].length + 1 == words[i].length AND words[j] is a predecessor of words[i]:
        • Update dp[i] = max(dp[i], dp[j] + 1)
  4. Return the maximum value in dp

Code

class Solution {
public:
    bool isPredecessor(const string& a, const string& b) {
        if (a.size() + 1 != b.size()) return false;
        int i = 0;
        for (int j = 0; j < (int)b.size(); j++) {
            if (i < (int)a.size() && a[i] == b[j]) i++;
        }
        return i == (int)a.size();
    }

    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });
        int n = words.size();
        vector<int> dp(n, 1);
        int result = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (isPredecessor(words[j], words[i])) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};
class Solution:
    def longestStrChain(self, words: list[str]) -> int:
        words.sort(key=len)
        n = len(words)
        dp = [1] * n
        result = 1

        def is_predecessor(a: str, b: str) -> bool:
            if len(a) + 1 != len(b):
                return False
            i = 0
            for ch in b:
                if i < len(a) and a[i] == ch:
                    i += 1
            return i == len(a)

        for i in range(1, n):
            for j in range(i):
                if is_predecessor(words[j], words[i]):
                    dp[i] = max(dp[i], dp[j] + 1)
            result = max(result, dp[i])

        return result
class Solution {
    private boolean isPredecessor(String a, String b) {
        if (a.length() + 1 != b.length()) return false;
        int i = 0;
        for (int j = 0; j < b.length(); j++) {
            if (i < a.length() && a.charAt(i) == b.charAt(j)) i++;
        }
        return i == a.length();
    }

    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        int n = words.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int result = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (isPredecessor(words[j], words[i])) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n² × L)

We have two nested loops over the words array: the outer loop runs n times, and for each iteration the inner loop runs up to i times (at most n-1). For each pair (i, j), the predecessor check scans the longer word character by character, costing O(L) where L is the maximum word length (up to 16). Total: O(n²) pairs × O(L) per check = O(n² × L).

With n ≤ 1000 and L ≤ 16: approximately 1000² × 16 = 16,000,000 operations — feasible but not optimal.

Space Complexity: O(n)

The dp array uses O(n) space. Sorting uses O(log n) additional space. Total auxiliary space is O(n).

Why This Approach Is Not Efficient

The LIS-style DP runs in O(n² × L) time. While this is a massive improvement over the exponential brute force, the quadratic factor in n means that for each word we check every previous word to see if it's a predecessor.

But think about it: a word of length 5 can only have predecessors of length 4. There is no point comparing it against words of length 1, 2, or 3 — those are too short to be direct predecessors. The O(n²) loop wastes time on pairs whose lengths are incompatible.

Moreover, the predecessor check itself can be done in reverse: instead of scanning all previous words and checking if they are predecessors, we can take the current word, remove one character at a time, and look up the resulting shorter word. If we store all previously seen words in a hash map, each lookup is O(1) amortized.

Since each word has at most L characters, we perform at most L lookups per word — giving us O(n × L) lookups total, each costing O(L) for string operations. This yields O(n × L²) total time, which for L ≤ 16 is dramatically faster than O(n² × L).

Optimal Approach - Hash Map DP

Intuition

The key insight is to reverse the predecessor relationship. Instead of asking "which previous word is a predecessor of the current word?", we ask "if I remove one character from the current word, does the resulting shorter word exist in my collection?"

Think of it like a word-shrinking game. You take a word like "bdca" and try removing one character at a time:

  • Remove 'b' → "dca" — is that a known word? No.
  • Remove 'd' → "bca" — is that a known word? Yes! And its best chain length is 3.
  • Remove 'c' → "bda" — is that a known word? Yes! Its best chain length is also 3.
  • Remove 'a' → "bdc" — is that a known word? No.

The best predecessor has chain length 3, so "bdca" gets chain length 3 + 1 = 4.

By storing word → chain_length in a hash map, every lookup is O(1) amortized. For each word, we make at most L deletions (where L is the word length, at most 16), so the total work per word is O(L²) — creating the substring costs O(L) and we do it L times.

This eliminates the need to compare every pair of words, replacing the O(n²) inner loop with an O(L²) inner loop that is independent of n.

Step-by-Step Explanation

Let's trace with words = ["a", "b", "ba", "bca", "bda", "bdca"] (sorted by length).

Initialize an empty hash map dp.

Step 1: Process "a" (length 1). Try removing each character:

  • Remove char at index 0 → "" (empty string, not in map)
  • No valid predecessor found. dp["a"] = 1. Map: {"a": 1}

Step 2: Process "b" (length 1). Remove char 0 → "" (not in map). dp["b"] = 1. Map: {"a": 1, "b": 1}

Step 3: Process "ba" (length 2). Remove char 0 ('b') → "a". Look up "a" in map → found with value 1! Candidate = 1 + 1 = 2.

Step 4: Remove char 1 ('a') → "b". Look up "b" in map → found with value 1! Candidate = max(2, 1+1) = 2. dp["ba"] = 2. Map: {"a": 1, "b": 1, "ba": 2}

Step 5: Process "bca" (length 3). Remove 'b' → "ca" (not in map). Remove 'c' → "ba" → found with value 2! Candidate = 3. Remove 'a' → "bc" (not in map). dp["bca"] = 3.

Step 6: Process "bda" (length 3). Remove 'b' → "da" (not in map). Remove 'd' → "ba" → found with value 2! dp["bda"] = 3.

Step 7: Process "bdca" (length 4). Remove 'b' → "dca" (not found). Remove 'd' → "bca" → found with value 3! Candidate = 4.

Step 8: Remove 'c' → "bda" → found with value 3! Candidate = max(4, 4) = 4. Remove 'a' → "bdc" (not found). dp["bdca"] = 4.

Result: Maximum value in map = 4.

Hash Map DP — Remove One Character and Look Up — Watch how we process each word by removing characters one at a time and looking up the shorter string in the hash map, building chain lengths incrementally.

Algorithm

  1. Sort words by length (ascending)
  2. Create an empty hash map dp (word → longest chain length ending at that word)
  3. Initialize result = 1
  4. For each word in the sorted list:
    • Set dp[word] = 1 (default: the word alone is a chain of length 1)
    • For each index i from 0 to len(word) - 1:
      • Create prev by removing the character at index i from word
      • If prev exists in dp:
        • Update dp[word] = max(dp[word], dp[prev] + 1)
    • Update result = max(result, dp[word])
  5. Return result

Code

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });

        unordered_map<string, int> dp;
        int result = 1;

        for (const string& word : words) {
            dp[word] = 1;
            for (int i = 0; i < (int)word.size(); i++) {
                string prev = word.substr(0, i) + word.substr(i + 1);
                if (dp.count(prev)) {
                    dp[word] = max(dp[word], dp[prev] + 1);
                }
            }
            result = max(result, dp[word]);
        }
        return result;
    }
};
class Solution:
    def longestStrChain(self, words: list[str]) -> int:
        words.sort(key=len)
        dp = {}
        result = 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)
            result = max(result, dp[word])

        return result
class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> dp = new HashMap<>();
        int result = 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));
                }
            }
            result = Math.max(result, dp.get(word));
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × L²)

We process each of the n words exactly once. For each word of length L, we try removing each of its L characters, creating a substring of length L-1 (which costs O(L) time). Each hash map lookup is O(L) amortized (hashing the string). Total: n words × L removals × L string cost = O(n × L²).

With n ≤ 1000 and L ≤ 16: approximately 1000 × 16² = 256,000 operations — extremely fast compared to the O(n² × L) = 16,000,000 of the LIS approach.

Space Complexity: O(n × L)

The hash map stores up to n entries, each with a string key of length at most L. Sorting requires O(log n) space. Total: O(n × L).