One of the top 100 Google questions: the longest chain

A very populate Google interview question, here it is: https://leetcode.com/problems/longest-string-chain/

1048. Longest String Chain

Medium

Given a list of words, each word consists of English lowercase letters.

Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.  For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Note:

1. 1 <= words.length <= 1000
2. 1 <= words[i].length <= 16
3. words[i] only consists of English lowercase letters.

The approach should be the reverse order: build the chains from the longest strings to the shortest by deleting characters. Here is the algorithm:
1. Build a cache for the words (hash table)
2. Create a function that, given a word, finds out the longest chain starting with that word. This function will work by deleting chars one by one, checking whether the newly formed word (created by deleting the character) is in the cache (and whether the new word has not been seen yet) and then calling the function recursively
3. The outer function will then invoke (2) keeping track of the max chain thus far

Code is down below. Cheers, ACC.

public class Solution
{
    public int LongestStrChain(string[] words)
    {
        Hashtable cache = new Hashtable();

        foreach (string w in words)
        {
            if (!cache.ContainsKey(w)) cache.Add(w, true);
        }

        int max = 0;
        foreach (string w in words)
        {
            int currentMaxChain = 0;
            MaxChain(w, cache, new Hashtable(), 1, ref currentMaxChain);
            max = Math.Max(max, currentMaxChain);
        }

        return max;
    }

    private void MaxChain(string currentWord,
                            Hashtable cache,
                            Hashtable seen,
                            int currentChain,
                            ref int maxChain)
    {
        maxChain = Math.Max(maxChain, currentChain);

        if (currentWord.Length == 1) return;

        for (int i = 0; i < currentWord.Length; i++)
        {
            string next = currentWord.Remove(i, 1);
            if (!seen.ContainsKey(next) && cache.ContainsKey(next))
            {
                seen.Add(next, true);
                MaxChain(next, cache, seen, currentChain + 1, ref maxChain);
                seen.Remove(next);
            }
        }
    }
}