# Leetcode 1048. Longest String Chain

# 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:** 4

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

**Example 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"].

**Example 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**

`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

- Sort the input array based on increasing length.
- Make use of a hashmap where the key stores the string and the values holds the maximum word chain length.
- Traverse through the string.
- Each string can be a word chain of chain length = 1. So populate the hashmap as
`map.put(currentString , 1)`

. - Now traverse through each and every character of the current string and delete each of the character.
- 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.
- 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.