FastPrep
Problem · Dynamic Programming

Longest String Chain

Learn this problem
● MediumLinkedIn logoLinkedInFULLTIMEOA

Problem statement

LC 1048 :)

The other question is shown in the img below:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

You are given an array of words where each word consists of lowercase English letters.

word₁ is a predecessor of word₂ if and only if we can insert exactly one letter anywhere in word₁ without changing the order of the other characters to make it equal to word₂.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcaa".

A word chain is a sequence of words [word₁, word₂, ..., wordₖ] with k >= 1, where word₁ is a predecessor of word₂, word₂ is a predecessor of word₃, and so on. A single word is trivially a word chain with k = 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Function

longestStrChain(words: String[]) → int

Examples

Example 1

words = ["a","b","ba","bca","bda","bdca"]return = 4

One of the longest word chains is ["a","ba","bda","bdca"].

Example 2

words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]return = 5

All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3

words = ["abcd","dbqca"]return = 1

The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

Constraints

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

More LinkedIn problems

drafts saved locally
public int longestStrChain(String[] words) {
  // write your code here
}
words["a","b","ba","bca","bda","bdca"]
expected4
checking account