Longest Chain

Problem Statement

Longest Chain Problem Description You are given a dictionary of n words. A chain is a sequence of dictionary words in which each word is obtained from the next one by deleting exactly one character, and every word of the sequence is itself in the dictionary. Every single word is already a chain of length 1 . Each time a character can be removed and the result is still a dictionary word, the chain grows by one. Determine the length of the longest chain the dictionary allows. Input Format The first line contains the integer n , the number of words. Each of the next n lines contains one word. Output Format Print a single integer: the length of the longest chain. Constraints 1 <= n <= 1000 1 <= |words[i]| <= 20 Each word is made of lowercase English letters only. The words are distinct. Examples Example 1 Input: 6 a ba bca bda bdca b Output: 4 Explanation: one longest chain is a -> ba -> bda -> bdca . Each step inserts one character going forward, that is, deletes one