DSA Tracker

Visualize

Longest String Chain

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)

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.

Details

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.

Problem:Longest String ChainMedium

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

step 1 / 7

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

Every step in words

Show all 7 steps
  1. 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.
  2. None of the 1 single-letter deletions of "b" land on a word already in the dictionary, so it starts its own chain: dp["b"] = 1.
  3. "ba" deletes one letter down to "a", which is already in the dictionary with a chain of 1: dp["ba"] = dp["a"] + 1 = 2.
  4. "bca" deletes one letter down to "ba", which is already in the dictionary with a chain of 2: dp["bca"] = dp["ba"] + 1 = 3.
  5. "bda" deletes one letter down to "ba", which is already in the dictionary with a chain of 2: dp["bda"] = dp["ba"] + 1 = 3.
  6. "bdca" deletes one letter down to "bca", which is already in the dictionary with a chain of 3: dp["bdca"] = dp["bca"] + 1 = 4.
  7. Longest chain ends at "bdca" with length 4 — the answer is the biggest value in the whole dp row, not the last column.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest String Chain in the editorAll Dynamic Programming problemsBack to roadmap