Longest String Chain

Medium20–25 min

Topics

Dynamic ProgrammingStringHashMap

Companies

AmazonGoogleAdobe

Given a list of distinct lowercase words, find the length of the longest chain that can be built from them. A word continues the chain if it can be produced from the previous word by adding a single extra letter somewhere in the middle — the rest of the original spelling has to stay in the same relative sequence. Framed in reverse, a word belongs right after whichever word remains once exactly one of its own letters is deleted. So the longest chain ending at any given word is just one more than the longest chain ending at the best such shorter word — provided that shorter word is actually present in the list. Since every predecessor is always exactly one letter shorter, processing the words from shortest to longest guarantees that by the time a word is reached, every string it could possibly extend has already been fully solved.

Test Case 1:

Input:words = ["o", "t", "to", "ton", "tan", "tone"]

Output:4

Explanation:o → to → ton → tone (each step inserts exactly one letter) is a chain of length 4, the longest possible here.

Test Case 2:

Input:words = ["xy", "xay", "xzay", "wxzay", "wxzayq"]

Output:5

Explanation:xy → xay → xzay → wxzay → wxzayq inserts one letter at a time — every word in the list is used, giving a chain of length 5.

Test Case 3:

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

Output:1

Explanation:Removing any single letter from "dbqca" never produces "abcd", so neither word can extend the other — the best chain is just one word by itself.

Constraints

◆1 ≤ words.length ≤ 8
◆1 ≤ words[i].length ≤ 8
◆words[i] consists of lowercase English letters
◆All the strings in words are distinct

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

A word can only ever follow a predecessor formed by deleting exactly one of its own letters — inserting one letter into the predecessor recovers the word, keeping every other letter's order intact. So for any word, the longest chain ending there is 1 plus the best chain achievable by whichever single-letter deletion also happens to be present in the given list — or just 1, if none of its deletions are present at all. Trying every word as the potential end of the chain and recursively chasing each one back through its usable deletions finds the answer, but the same shorter word gets re-explored from scratch every time a different longer word deletes down to it.

TimeO(n · 2^L)

SpaceO(L)

Java

Try it out

class Solution {
    private Set<String> wordSet;

    public int longestStrChain(String[] words) {
        wordSet = new HashSet<>(Arrays.asList(words));
        int best = 1;
        for (String w : words) {
            best = Math.max(best, solve(w));
        }
        return best;
    }

    private int solve(String word) {
        int best = 1;
        for (int i = 0; i < word.length(); i++) {
            String pred = word.substring(0, i) + word.substring(i + 1);
            if (wordSet.contains(pred)) {
                best = Math.max(best, 1 + solve(pred));
            }
        }
        return best;
    }
}

Optimal — Bottom-Up DP with a HashMap

Optimal

Sort the words shortest to longest, since every predecessor of a word is exactly one letter shorter and therefore must be processed earlier in that order. Let dp[word] hold the length of the longest chain that ends at word. For each word in sorted order, try every single-letter deletion of it; whenever that shorter string is a key already sitting in dp (meaning it's both one of the given words and already been processed), dp[word] can extend it by one. Recording each word's result the moment it's computed means later, longer words can just look their predecessors up in O(1) instead of re-deriving them.

TimeO(n · L)

SpaceO(n · L)