Leetcode: Longest String Chain

This is a question that was made by twosigma and other quantitative development firms. It is the "longest string chain" problem and it has been tested and evaluated in multiple trading firms such as two sigma. Here it is:

Given a list of words, each word consists of English lowercase letters. Let there be 2 words, named "word1" and "word2" and let's say "word1" is a predecessor of "word2" if and only if we can add exactly one letter to make "word1" equal to "word2".  For example "abc" is a predecessor to "abac" because we add a as the third character. Let a word chain be a sequence of words such that for words [word_1, word_2, ..., word_k] and we want to return the longest possible length of a word chain with the given list of words. 

Here's how to do it, I believe this is a dynamic programming problem:

Here are some examples:

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]

Output: 4

Explanation: One of the longest word chain is "a","ba","bda","bdca".

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]

Output: 5

 

Constraints:

1 <= words.length <= 1000

1 <= words[i].length <= 16

words[i] only consists of English lowercase letters.

I will put the explanation and the solution to this problem below.

First we want to sort all the words in the list be the length of the word, by applying bucket sort. For each word, loop on all possible previous words with 1 letter missing, and if we have seen this pervious word, update the longest chain, and finally figure out the longest word change. 

Bucket Sort | GeeksForGeeks

In this sorting algorithm, buckets are created to put elements into them. Then, we apply some sorting algorithms to sort the elements in each bucket. Finally, take them out and join them to get the sorted array. 

So let's say the Total number of elements are n = 10. Therefore, we create 10 buckets.

0.78 - 0.17 - 0.39 - 0.26 - 0.72 - 0.94 - 0.21 - 0.12 - 0.23 - 0.68

Then we insert arr[i] to bucket[n * arr[i]]. After this, we sort each bucket using insertion sort. 

Here is where we are at now

Index 0:

Index 1: 0.12 --> 0.17

Index 2: 0.21 --> 0.23 --> 0.26

Index 3: 0.39

Index 4:

Index 5:

Index 6: 0.68

Index 7: 0.78 --> 0.72

Index 8:

Index 9: 0.94

Now, we sort each bucket individually using insertion sort. Here's the final answer after arranging each the indices:

0.12 - 0.17 - 0.21 - 0.23 - 0.26 - 0.39 - 0.68 - 0.72 - 0.78 - 0.94

Here's the algorithm for bucket sort. 

void bucketSort(float arr[]. int n) {

    

    vector<float>b[n];

    for(int i = 0; i < n; i++){

        int bi = n * arr[i];

        b[bi].push_back(arr[i]);

    }

    for(int i = 0; i < n; i++)

        sort(b[i].begin(), b[i].end());

    int index = 0;

    for(int i = 0; i < n; i++)

        for(int j = 0; j < b[i].size(); i++) {

            arr[index++] = b[i][j];

        }

}

Which in real life we would just perform the Arrays.sort() operation. So for each word, loop on all possible previous words and see if there's a match and a word chain. If we have seen this word, we will upload the longest chain for the word. We finally finish by returning the longest word chain.

 public int longestStrChain(String[] words) {

        Map<String, Integer> dp = new HashMap<>(); 

        //Sort the arrays by length by using bucket sort. 

        Arrays.sort(words, (a, b)->a.length() - b.length());

        //final result of the longest chain to return.

        int res = 0;

        //iterate through all the strings. 

        for (String word : words) {g

            //best substring

            int best = 0;

            //get the previous substring

            for (int i = 0; i < word.length(); ++i) {

                //delete each character one by one in the word

                String prev = word.substring(0, i) + word.substring(i + 1);

                //update the best integer with following word by comparing it to the best length of the word character as accessed in the HashMap. 

                best = Math.max(best, dp.getOrDefault(prev, 0) + 1);

            }

            dp.put(word, best);

            //see if the best substring gets updated

            res = Math.max(res, best);

        }

        return res;

    }