Longest String Chain

MediumDynamic Programming1d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Word a is a **predecessor** of word b when you can insert exactly one letter anywhere into a (without changing the order of its other letters) to obtain b. For example, "ac" is a predecessor of "abc", but "cb" is not a predecessor of "abc". A **word chain** is a sequence w1, w2, ..., wk with k >= 1 where each word is a predecessor of the next. A single word is a chain of length 1. Given a list of distinct lowercase words, pick words from it (in any order) to form the longest chain and return that length.

Examples

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
One longest chain is "a" -> "ba" -> "bda" -> "bdca".
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
"xb" -> "xbc" -> "cxbc" -> "pcxbc" -> "pcxbcf" uses every word.
Input: words = ["abcd","dbqca"]
Output: 1
"abcd" is not a predecessor of "dbqca" because the order changes.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • words[i] consists of lowercase English letters
  • all words are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 1d dp problems