# Problem Statement

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

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

• For example, `"abc"` is a predecessor of `"abac"`, while `"cba"` is not a predecessor of `"bcad"`.

A word chain is a sequence of words `[word1, word2, ..., wordk]` with `k >= 1`, where `word1` is a predecessor of `word2`, `word2` is a predecessor of `word3`, 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`.

# Test Cases

Example 1:

`Input: words = ["a","b","ba","bca","bda","bdca"]Output: 4Explanation: One of the longest word chains is ["a","ba","bda","bdca"].`

Example 2:

`Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]Output: 5Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].`

Example 3:

`Input: words = ["abcd","dbqca"]Output: 1Explanation: 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.

# Approach

Our task is to find the longest possible word chain where word chain means a sequence of words say [word1,word2,word3….] where word1 is a predecessor of word2, word2 is a predecessor of word3 and so on.

A single word is also considered to be a word chain of length 1.

So one of the observation we can do is we can actually sort the given string array based on the length so that we can easily check for the predecessor property.

Also we need to have a fast look up data structure in order to see if removal of a character from a particular string actually accounts for the word chain and increases the word chain length.

## Algorithm

1. Sort the input array based on increasing length.
2. Make use of a hashmap where the key stores the string and the values holds the maximum word chain length.
3. Traverse through the string.
4. Each string can be a word chain of chain length = 1. So populate the hashmap as `map.put(currentString , 1)` .
5. Now traverse through each and every character of the current string and delete each of the character.
6. Check inside the hashmap whether the string formed after deleting the char is present and its chain length is the maximum. If yes update the hashmap with the maximum length.
7. Update the final maximum chain length.

# Time and Space Complexity

At first we are sorting the given array which have a time complexity say O(nlogn) where n = length of the string array.

Also we are traversing through each and every string inside the array and each and every character of the current string. Also we are also doing a delete operation of every ith character. This makes our time complexity to be
O(n * l²) where n = length of string array, l = max(stringlength).

NOTE : We have l² as we need to traverse through each and every character of string and delete each of the character.

So time complexity = O(nlogn) + O(n*l²)

For space complexity we are making use of extra space to store each and every string inside the array and also we are creating a new string each time after deleting the character.
So Space complexity will be O(n * l) where n= length of string array and l = max(stringlength).

Please correct me if there is any error regarding the complexity analysis.

# Code 