Problem statement

wordA is a predecessor of wordB if inserting exactly one letter somewhere in wordA — without reordering the rest — produces wordB.

A word chain is a sequence where each word is a predecessor of the next. Given an array of words, return the length of the longest possible chain.

Example 1

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One longest chain is "a" → "ba" → "bda" → "bdca".

Example 2

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

Example 3

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

Constraints

• 1 <= words.length <= 20
• 1 <= words[i].length <= 8
• words[i] consists of lowercase English letters.

Hints for Longest String Chain

1. Hint 1

   A predecessor is always exactly one character shorter, so sort by length and the chain only ever moves forward.

2. Hint 2

   best[i] is the longest chain ending at word i; extend it from any earlier word that is a predecessor.

3. Hint 3

   Checking the predecessor relation is a two-pointer walk allowing a single skip in the longer word.

How to solve Longest String Chain

A predecessor is exactly one character shorter, so sort by length; best[i] is the longest chain ending at word i, extended from any shorter word that is a predecessor.

Approach

1. Sort words by length.
2. For each i, for each earlier j, if words[j] is a predecessor of words[i], best[i] = max(best[i], best[j] + 1).
3. Return the maximum.

Why it works

Chains strictly increase in length, so after sorting every predecessor precedes its successor and the LIS-style recurrence sees all candidates. The predecessor test is a two-pointer walk allowing one skip in the longer word.

Complexity

• Time — O(n² · L)
• Space — O(n)

Pitfalls

• A hash-map variant — delete each character of the word and look up the result — runs in O(n · L²) and scales better.

Reference solution

Python

def longestStrChain(words) -> int:
    def is_predecessor(a, b):
        if len(b) != len(a) + 1:
            return False
        i = j = skips = 0
        while i < len(a) and j < len(b):
            if a[i] == b[j]:
                i += 1
                j += 1
            else:
                skips += 1
                j += 1
                if skips > 1:
                    return False
        return True

    ordered = sorted(words, key=len)
    best = [1] * len(ordered)
    answer = 1
    for i in range(len(ordered)):
        for j in range(i):
            if is_predecessor(ordered[j], ordered[i]):
                best[i] = max(best[i], best[j] + 1)
        answer = max(answer, best[i])
    return answer

Java

public static int longestStrChain(String[] words) {
    String[] sorted = Arrays.copyOf(words, words.length);
    Arrays.sort(sorted, new Comparator<String>() {
        public int compare(String a, String b) { return a.length() - b.length(); }
    });
    int n = sorted.length;
    int[] best = new int[n];
    Arrays.fill(best, 1);
    int answer = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (isPredecessorChain(sorted[j], sorted[i]) && best[j] + 1 > best[i]) best[i] = best[j] + 1;
        }
        if (best[i] > answer) answer = best[i];
    }
    return answer;
}

private static boolean isPredecessorChain(String a, String b) {
    if (b.length() != a.length() + 1) return false;
    int i = 0, j = 0, skips = 0;
    while (i < a.length() && j < b.length()) {
        if (a.charAt(i) == b.charAt(j)) { i++; j++; }
        else {
            skips++;
            j++;
            if (skips > 1) return false;
        }
    }
    return true;
}

C++

static bool isPredecessorChain(const string& a, const string& b) {
    if (b.size() != a.size() + 1) return false;
    size_t i = 0, j = 0;
    int skips = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] == b[j]) { i++; j++; }
        else {
            skips++;
            j++;
            if (skips > 1) return false;
        }
    }
    return true;
}

int longestStrChain(vector<string>& words) {
    vector<string> sorted = words;
    sort(sorted.begin(), sorted.end(), [](const string& a, const string& b) {
        return a.size() < b.size();
    });
    int n = (int) sorted.size();
    vector<int> best(n, 1);
    int answer = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (isPredecessorChain(sorted[j], sorted[i]) && best[j] + 1 > best[i]) best[i] = best[j] + 1;
        }
        answer = max(answer, best[i]);
    }
    return answer;
}

JavaScript

var longestStrChain = function(words) {
    const isPredecessor = function(a, b) {
        if (b.length !== a.length + 1) return false;
        let i = 0, j = 0, skips = 0;
        while (i < a.length && j < b.length) {
            if (a[i] === b[j]) { i++; j++; }
            else {
                skips++;
                j++;
                if (skips > 1) return false;
            }
        }
        return true;
    };
    const sorted = words.slice().sort(function(a, b) { return a.length - b.length; });
    const best = new Array(sorted.length).fill(1);
    let answer = 1;
    for (let i = 0; i < sorted.length; i++) {
        for (let j = 0; j < i; j++) {
            if (isPredecessor(sorted[j], sorted[i]) && best[j] + 1 > best[i]) best[i] = best[j] + 1;
        }
        if (best[i] > answer) answer = best[i];
    }
    return answer;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium