Pattern visualizer

Longest String Chain

Searching forward from a word by inserting every one of 26 letters at every position is expensive and hard to order. Flip it: sort words shortest-first, then for each word delete one character at a time (only L ways, not 26*L) and check whether that shorter word is already in the dictionary. If it is, this word can extend whatever chain ended there, so dp[word] = 1 + dp[best predecessor found], or just 1 if none exists. Animated on: words = ["a","b","ba","bca","bda","bdca"] — a word A is a predecessor of B if inserting exactly one letter into A makes B. Find the longest chain of words where each is a predecessor of the next..

Sort by length, then delete one letter at a time to find the predecessor already in dp

time O(n log n + n * L^2)space O(n * L)step 1 / 7

abbabcabdabdca

chain len

line 6

None of the 1 single-letter deletions of "a" land on a word already in the dictionary, so it starts its own chain: dp["a"] = 1.

Pseudocode

1FUNCTION longestStrChain(words):
2  SORT words BY LENGTH ascending
3  dp <- empty map
4  best <- 1
5  FOR EACH word IN words:
6    dp[word] <- 1
7    FOR i FROM 0 TO LENGTH(word) - 1:
8      pred <- word WITH CHARACTER AT i REMOVED
9      IF pred IN dp:
10        dp[word] <- MAX(dp[word], dp[pred] + 1)
11    best <- MAX(best, dp[word])
12  RETURN best

← / → step · space play · Home restart

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap