Dynamic Programming • Hash Maps

Longest String Chain

Given a list of words, find the length of the longest chain where each word adds exactly one letter anywhere to the previous word.

Try Interactive Simulator

Overview

This is a variation of LIS, but on strings. Instead of checking every previous word, we systematically remove one character to find predecessors.

Sorting

Because a predecessor must be strictly shorter, we first sort the array of words by length. This guarantees we process predecessors before successors.

Hash Map DP

Instead of an array `dp[i]`, we use a hash map `dp[word]` mapping the string to its chain length. This provides O(1) lookups for predecessors.

The Transition

For a word, loop through each character, remove it, and check if the resulting string is in the hash map. Update the max length accordingly.

Current Word

...

➔

Testing Predecessor

...

DP Hash Map State

Code Tracker

:::

1words.sort((a, b) => a.length - b.length);

2let dp = new Map();

3for (let word of words) {

4 let best = 1;

5 for (let i = 0; i < word.length; i++) {

6 let prev = word.slice(0, i) + word.slice(i+1);

7 if (dp.has(prev)) {

8 best = Math.max(best, dp.get(prev) + 1);

9 }

10 }

11 dp.set(word, best);

12}