Longest String Chain

Problem Statement

Given a list of words, find the length of the longest chain where each subsequent word is formed by adding exactly one letter to the previous word at any position.

A word chain is valid if: word1 -> word2 -> ... -> wordN, where each word(i+1) is a predecessor of word(i).

Word A is a predecessor of B if B can be formed by adding exactly one letter to A.

Input Format

Line 1: Number of words. Following lines: One word per line.

Output Format

Length of the longest string chain.

Examples

Example 1:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4

Chain: "a" -> "ba" -> "bda" -> "bdca"