Leetcode 1048. Longest String Chain

Java Accepted Code

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

  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

Java Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohith Vazhathody

Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.