☕ DSA Java Articles

Topics › Dynamic Programming › DP on LIS

Longest String Chain

Medium TUF ID 640 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of lowercase words. Word A is a predecessor of word B if you can insert exactly one letter anywhere in A, without reordering the other letters, to get B. For example "abc" is a predecessor of "abac", but "cba" is not a predecessor of "bcad". A word chain is a sequence w1, w2, ..., wk where each word is a predecessor of the next. Using words from the array (each at most once, in any order), return the length of the longest possible chain. A single word is a chain of length 1.

Constraints: 1 ≤ n ≤ 1000, 1 ≤ word length ≤ 16. The Java file returns 0 for an empty array.

Example 1

words = ["a", "b", "ba", "bca", "bda", "bdca"]
answer = 4          // "a" -> "ba" -> "bda" -> "bdca"

Example 2

words = ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]
answer = 5          // "xb" -> "xbc" -> "cxbc" -> "pcxbc" -> "pcxbcf"

Each step in a chain adds exactly one letter, so lengths go up by one at every step. That gives the natural processing order: by length. After sorting by length, a chain is a subsequence in which consecutive words satisfy the predecessor relation, which is an LIS with a custom comparison.

Approach 1: Brute force recursion

Intuition. Look at the chain from its end. The word before w in a chain must be w with one letter deleted. A word of length L has only L such deletions, so try each one, and if the shorter word is in the array, recursively find the longest chain ending there. The answer is the best over all possible final words.

Algorithm.

  1. Put all words in a hash set.
  2. For each word w, compute chainEndingAt(w): start at 1; for every position i, delete letter i, and if the result is in the set, try 1 + chainEndingAt(shorter).
  3. Return the maximum.
static int bruteForce(String[] words) {
    Set<String> dict = new HashSet<>(Arrays.asList(words));
    int best = 0;
    for (String w : words) best = Math.max(best, chainEndingAt(w, dict));
    return best;
}

static int chainEndingAt(String w, Set<String> dict) {
    int best = 1;
    for (int i = 0; i < w.length(); i++) {
        String shorter = w.substring(0, i) + w.substring(i + 1);   // delete letter i
        if (dict.contains(shorter)) best = Math.max(best, 1 + chainEndingAt(shorter, dict));
    }
    return best;
}

Complexity. Without caching, the same shorter word is re-solved many times. A word of length L can branch up to L ways, then L - 1, and so on, so the worst case is about O(n · L!) string operations. Fine for the tests, hopeless for L = 16.

Approach 2: Better, LIS with a predecessor check

Intuition. Sort the words by length. Now every chain appears in left-to-right order, so define dp[i] = length of the longest chain ending at w[i], exactly like “LIS ending at i”:

dp[i] = 1 + max(dp[j]) over j < i where w[j] is a predecessor of w[i]   (or 1)

The only new ingredient is the comparison. isPredecessor(shorter, longer) first checks that the lengths differ by exactly one. Then it walks both strings with two pointers: advance in shorter whenever the letters match, always advance in longer. If all of shorter gets matched, shorter is a subsequence of longer; with lengths differing by one, that means exactly one letter was inserted.

Sorting is essential. Without it, a predecessor might appear after the word it precedes, and the j < i loop would never see it.

Algorithm.

  1. Sort a copy of the words by length.
  2. For each i, set dp[i] = 1, then for each j < i with isPredecessor(w[j], w[i]), take dp[j] + 1 if larger.
  3. Return the maximum dp[i].
static int lisStyle(String[] words) {
    String[] w = words.clone();
    Arrays.sort(w, Comparator.comparingInt(String::length));
    int n = w.length, best = 0;
    int[] dp = new int[n];                                          // dp[i] = longest chain ending at w[i]
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (isPredecessor(w[j], w[i])) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

static boolean isPredecessor(String shorter, String longer) {
    if (longer.length() != shorter.length() + 1) return false;
    int i = 0;                                                      // next letter of shorter to match
    for (int j = 0; j < longer.length(); j++) {
        if (i < shorter.length() && shorter.charAt(i) == longer.charAt(j)) i++;
    }
    return i == shorter.length();                                   // all of shorter matched; one letter of longer skipped
}

Complexity. Time O(n log n + n^2 · L): n^2 pairs, each compared in O(L). Space O(n). For n = 1000 and L = 16 that is about 1.6 × 10^7 character steps, which passes.

Approach 3: Optimal, deletions with a hash map

Intuition. Approach 2 compares each word with every shorter word, but a word of length L has only L possible predecessors: the strings obtained by deleting one letter. Instead of searching for predecessors, generate them and look them up. Process words by increasing length and store longest[word] = longest chain ending at that word. When we reach a word, all its possible predecessors are shorter, so their values are already in the map.

This is the same recurrence as Approach 2, with the inner loop over j replaced by L hash lookups. It is also Approach 1 with memoization, computed bottom-up.

Algorithm.

  1. Sort a copy of the words by length.
  2. For each word: cur = 1; for each position i, form shorter by deleting letter i; if longest contains it, cur = max(cur, longest[shorter] + 1). Store longest[word] = cur.
  3. Return the largest cur.
static int hashMapDp(String[] words) {
    String[] w = words.clone();
    Arrays.sort(w, Comparator.comparingInt(String::length));
    Map<String, Integer> longest = new HashMap<>();                 // word -> longest chain ending at it
    int best = 0;
    for (String word : w) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            String shorter = word.substring(0, i) + word.substring(i + 1);
            Integer prev = longest.get(shorter);
            if (prev != null) cur = Math.max(cur, prev + 1);
        }
        longest.put(word, cur);
        best = Math.max(best, cur);
    }
    return best;
}

Dry run on ["a", "b", "ba", "bca", "bda", "bdca"] (already sorted by length):

word deletions found in map longest[word]
a (empty string) not present 1
b (empty string) not present 1
ba “a” → 1, “b” → 1 2
bca “ba” → 2 3
bda “ba” → 2 3
bdca “bca” → 3, “bda” → 3 4

The answer is 4.

Complexity. Time O(n log n + n · L^2): each word generates L deletions of length L - 1 and hashes them. Space O(n · L) for the map. With L ≤ 16 this is much faster than comparing all pairs.

Edge cases and pitfalls