FastPrepLongest String Chain

Longest String Chain

Visa logoVisa● MediumNEW GRADINTERNOA
Learn

Problem statement

You are given an array of lowercase words words representing a dictionary.

A string chain starts with one dictionary word. At each step, remove exactly one character from the current word. The resulting word must also be present in the dictionary.

Return the maximum number of words in any valid chain. A single dictionary word forms a chain of length 1.

FastPrep practice interpretation: Repeated copies of the same word do not create extra chain positions; membership is determined by distinct word values.

Function

longestChain(words: String[]) → int

Examples

Example 1

words = ["a","and","an","bear"]return = 3

The chain ["and", "an", "a"] removes one character at each step and has length 3.

Example 2

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

One longest chain is ["bdca", "bda", "ba", "a"].

Example 3

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

Neither word becomes the other by deleting one character, so the longest chain contains one word.

Constraints

  • 1 <= words.length <= 50000
  • 1 <= words[i].length <= 60
  • Every word contains only lowercase English letters from a through z.

Source note: The source slide shows the HackerRank statement, example, function name, return type, and constraints.

More Visa problems

See Visa hiring insights
public int longestChain(String[] words) {
  // Write your code here.
}
words["a","and","an","bear"]
expected3
Checking account…