Naive Solutions

We could go through all possible chains and check if each works, or we could use a recursive function that adds one character every time, but these solutions are too slow.

$\mathcal{O}(n^2 L^2)$ Dynamic Programming Solution

Let's build a chain from the shortest string to the longest string. Say we currently have the chain $(\text{w}_1, \text{w}_2, \ldots, \text{w}_{k-1}, \text{w}_k)$. We see that it doesn't matter what any of the words before $\text{w}_k$ are, only that there are $k$ of them. This suggests a dynamic programming solution, where $\text{dp}[i]=$ the length of the longest chain that ends with the string $\text{words}[i]$.

First sort $\text{words}$ by increasing length. An outer loop will loop $\text{current\_word\_index}$. For each $\text{current\_word\_index}$, we have an inner loop to check every word before it to see if it can be a predecessor. We'll call this index $\text{previous\_word\_index}$. If so, we update $\text{dp}[\text{current\_word\_index}]$ to $\max(\text{dp}[\text{current\_word\_index}], \text{dp}[\text{previous\_word\_index}]+1)$ because we can extend the chain ending in $\text{previous\_word}$ by appending $\text{current\_word}$.

For example, when $\text{words} = [\verb|"a"|, \verb|"ab"|, \verb|"cb"|, \verb|"cab"|]$, $\text{current\_word\_index}=3$, and $\text{previous\_word\_index}=1$, we find that removing $\verb|"c"|$ from $\text{words}[\text{current\_word\_index}] = \verb|"cab"|$ yields $\verb|"ab"| = \text{words}[\text{previous\_word\_index}]$.

Time complexity

Let $n =\text{words.length}$ and $L = \max\{\text{words[i].length}\}$.

Sorting takes $\mathcal{O}(n \log n)$.

Our nested loops take $\mathcal{O}(n^2)$ and call isPredecessor() that runs in $\mathcal{O}(L^2)$, so this part takes $\mathcal{O}(n^2L^2)$.

The total time complexity of this algorithm is therefore $\mathcal{O}(n \log n + n^2 L^2) = \mathcal{O}(n^2 L^2)$.

Space complexity

The $\text{dp}$ array consumes $\mathcal{O}(n)$ memory.

$\mathcal{O}(n^2 L^2)$ Solutions below

C++ Solution

class Solution {
  public:
	bool isPredecessor(string &previous_word, string &current_word) {
		if (previous_word.size() + 1 == current_word.size()) {
			for (int k = 0; k < current_word.size(); k++) {
				if (previous_word == current_word.substr(0, k) + current_word.substr(k + 1))
					return true;
			}
		}
		return false;
	}
	int longestStrChain(vector<string> &words) {
		// sort words by length
		sort(words.begin(), words.end(), [](auto x, auto y) { return x.size() < y.size(); });
		int n = words.size();
		vector<int> dp(n, 1);
		for (int current_word_index = 0; current_word_index < n; current_word_index++) {
			for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
				if (isPredecessor(words[j], words[current_word_index])) {
					dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1);
				}
			}
		}
		return *max_element(dp.begin(), dp.end());
	}
};

Java Solution

class Solution {
    public static boolean isPredecessor(String previous_word, String current_word) {
        if (previous_word.length() + 1 == current_word.length()) {
            for (int k = 0; k < current_word.length(); k++) {
                if (previous_word.equals(current_word.substring(0, k) + current_word.substring(k+1)))
                    return true;
            }
        }
        return false;
    }
    public int longestStrChain(String[] words) {
        // sort words by length
        Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
        int n = words.length;

        // add padding to words to avoid index out of bounds errors
        for (int i = 0; i < n; i++) {
            words[i] = "#" + words[i];
        }

        int ans = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int current_word_index = 0; current_word_index < n; current_word_index++) {
            for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
                if (isPredecessor(words[previous_word_index], words[current_word_index])) {
                    dp[current_word_index] = Math.max(dp[current_word_index], dp[previous_word_index] + 1);
                    ans = Math.max(ans, dp[current_word_index]);
                }

            }
        }
        return ans;
    }
}

Python Solution

class Solution:
    def isPredecessor(self, previous_word, current_word):
        if len(previous_word) + 1 == len(current_word):
            for k in range(len(current_word)):
                if previous_word == current_word[0:k] + current_word[k+1:]:
                    return True
        return False

    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        n = len(words)
        dp = [1 for _ in range(n)]
        for current_word_index in range(n):
            for previous_word_index in range(current_word_index):
                if self.isPredecessor(words[previous_word_index], words[current_word_index]):
                    dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1)
        return max(dp)

JavaScript Solution

var isPredecessor = function (previous_word, current_word) {
  if (previous_word.length + 1 == current_word.length) {
    for (let k = 0; k < current_word.length; k++) {
      if (
        previous_word ===
        current_word.slice(0, k) + current_word.slice(k + 1)
      )
        return true;
    }
  }
  return false;
};

/**
 * @param {string[]} words
 * @return {number}
 */
var longestStrChain = function (words) {
  // sort words by length
  words.sort((a, b) => a.length - b.length);
  n = words.length;
  dp = new Array(n).fill(1);

  for (
    let current_word_index = 0;
    current_word_index < n;
    current_word_index++
  ) {
    for (
      let previous_word_index = 0;
      previous_word_index < current_word_index;
      previous_word_index++
    ) {
      if (
        isPredecessor(words[previous_word_index], words[current_word_index])
      ) {
        dp[current_word_index] = Math.max(
          dp[current_word_index],
          dp[previous_word_index] + 1
        );
      }
    }
  }
  return Math.max(...dp);
};

$\mathcal{O}(n L^2)$ Dynamic Programming Solution (requires HashMap)

In our last solution, checking all previous words for predecessors was slow.

Observe that each word can only have $\mathcal{O}(L)$ predecessors, so we can generate them all (in $\mathcal{O}(L^2)$) and check the best $\text{dp}$ value we can get from them.

Let $\text{dp}[\text{str}]=$ the length of the longest chain that ends with the string $\text{str}$. $\text{dp}$ will be a hashmap to allow for $\mathcal{O}(1)$ retrieval by key.

As we did before, sort $\text{words}$ by increasing length. Loop through the current string $\text{current\_word}$. Then for each index $j$, let $\text{previous\_word}_j$ be $\text{current\_word}$ with its $j$th character removed. Set $\text{dp}[\text{current\_word}]$ to $\max\{\text{dp}[\text{previous\_word}_j]+1\}$. Our answer is the max of all entries in $\text{dp}$.

Time complexity

Let $n =\text{words.length}$ and $L = \max\{\text{words[i].length}\}$.

Sorting takes $\mathcal{O}(n \log n)$.

For every string (there are $\mathcal{O}(n)$ of them), create each of its predecessors in $\mathcal{O}(L^2)$ and check for their value in $\text{dp}$ in $\mathcal{O}(1)$. This comes together to $\mathcal{O}(nL^2)$.

The total time complexity is therefore $\mathcal{O}(n \log n + n L^2)$.

Space complexity

The $\text{dp}$ hashmap consumes $\mathcal{O}(n)$ memory.

Bonus:

We can perform counting sort in $\mathcal{O}(n+L)$, giving a total time complexity of $\mathcal{O}((n+L) + nL^2) = \mathcal{O}(nL^2)$.

$\mathcal{O}(n \log n + n L^2)$