FastPrepFastPrep
Problem Brief

Longest String Chain

FULLTIMEOA

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.

1Example 1

Input
words = ["a","b","ba","bca","bda","bdca"]
Output
4
Explanation

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

2Example 2

Input
words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output
5
Explanation

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

3Example 3

Input
words = ["abcd","dbqca"]
Output
1
Explanation

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

Limits and guarantees your solution can rely on.

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • words[i] only consists of lowercase English letters.
public int longestStrChain(String[] words) {
  // write your code here
}
Input

words

["a","b","ba","bca","bda","bdca"]

Output

4

Sign in to submit your solution.