Longest String Chain

medium dp hash map sorting

Problem

You are given an array of words. Word A is a predecessor of word B if you can insert exactly one letter anywhere in A (without reordering the rest) to make B. A word chain is a sequence where each word is a predecessor of the next. Return the length of the longest possible word chain that can be built from the given words.

Inputwords = ["a", "b", "ba", "bca", "bda", "bdca"]

Output4

One longest chain is "a" → "ba" → "bda" → "bdca", each adding one letter.

words (comma-separated)

def longest_str_chain(words):
    words.sort(key=len)
    best = {}
    longest = 0
    for w in words:
        cur = 1
        for i in range(len(w)):
            pred = w[:i] + w[i + 1:]
            if pred in best:
                cur = max(cur, best[pred] + 1)
        best[w] = cur
        longest = max(longest, cur)
    return longest

function longestStrChain(words) {
  words.sort((a, b) => a.length - b.length);
  const best = new Map();
  let longest = 0;
  for (const w of words) {
    let cur = 1;
    for (let i = 0; i < w.length; i++) {
      const pred = w.slice(0, i) + w.slice(i + 1);
      if (best.has(pred)) cur = Math.max(cur, best.get(pred) + 1);
    }
    best.set(w, cur);
    longest = Math.max(longest, cur);
  }
  return longest;
}

class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> best = new HashMap<>();
        int longest = 0;
        for (String w : words) {
            int cur = 1;
            for (int i = 0; i < w.length(); i++) {
                String pred = w.substring(0, i) + w.substring(i + 1);
                if (best.containsKey(pred)) cur = Math.max(cur, best.get(pred) + 1);
            }
            best.put(w, cur);
            longest = Math.max(longest, cur);
        }
        return longest;
    }
}

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> best;
    int longest = 0;
    for (const string& w : words) {
        int cur = 1;
        for (int i = 0; i < (int)w.size(); i++) {
            string pred = w.substr(0, i) + w.substr(i + 1);
            if (best.count(pred)) cur = max(cur, best[pred] + 1);
        }
        best[w] = cur;
        longest = max(longest, cur);
    }
    return longest;
}

Explanation

A chain grows by adding one letter at a time, so a longer word can only follow a shorter word. That single fact lets us sort the words by length and process them from shortest to longest, building chains as we go.

For each word w we ask: what is the longest chain ending here? To find its possible predecessors, we drop one letter at every position to get a shorter candidate pred. If we have already recorded a chain for that pred in the best map, then w can extend it: cur = best[pred] + 1.

We keep the largest such extension (default 1 if no predecessor exists), store it as best[w], and update the global longest. Because we sorted by length, every predecessor of w was already handled, so its answer is ready when we need it.

Dropping one letter is exactly the reverse of inserting one letter, which is how chains are defined, so this reliably links each word to its valid shorter forms.

Example: with ["a","b","ba","bca","bda","bdca"], dropping a letter from "bdca" yields "bda" (chain 3), giving "bdca" a chain of 4 along "a"→"ba"→"bda"→"bdca".

Time: O(n · L²) Space: O(n)