1048. Longest String Chain

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

1class Solution {
2  public:
3	bool isPredecessor(string &previous_word, string &current_word) {
4		if (previous_word.size() + 1 == current_word.size()) {
5			for (int k = 0; k < current_word.size(); k++) {
6				if (previous_word == current_word.substr(0, k) + current_word.substr(k + 1))
7					return true;
8			}
9		}
10		return false;
11	}
12	int longestStrChain(vector<string> &words) {
13		// sort words by length
14		sort(words.begin(), words.end(), [](auto x, auto y) { return x.size() < y.size(); });
15		int n = words.size();
16		vector<int> dp(n, 1);
17		for (int current_word_index = 0; current_word_index < n; current_word_index++) {
18			for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
19				if (isPredecessor(words[j], words[current_word_index])) {
20					dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1);
21				}
22			}
23		}
24		return *max_element(dp.begin(), dp.end());
25	}
26};

Java Solution

1class Solution {
2    public static boolean isPredecessor(String previous_word, String current_word) {
3        if (previous_word.length() + 1 == current_word.length()) {
4            for (int k = 0; k < current_word.length(); k++) {
5                if (previous_word.equals(current_word.substring(0, k) + current_word.substring(k+1)))
6                    return true;
7            }
8        }
9        return false;
10    }
11    public int longestStrChain(String[] words) {
12        // sort words by length
13        Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
14        int n = words.length;
15
16        // add padding to words to avoid index out of bounds errors
17        for (int i = 0; i < n; i++) {
18            words[i] = "#" + words[i];
19        }
20
21        int ans = 1;
22        int[] dp = new int[n];
23        Arrays.fill(dp, 1);
24        for (int current_word_index = 0; current_word_index < n; current_word_index++) {
25            for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
26                if (isPredecessor(words[previous_word_index], words[current_word_index])) {
27                    dp[current_word_index] = Math.max(dp[current_word_index], dp[previous_word_index] + 1);
28                    ans = Math.max(ans, dp[current_word_index]);
29                }
30
31            }
32        }
33        return ans;
34    }
35}

Python Solution

1class Solution:
2    def isPredecessor(self, previous_word, current_word):
3        if len(previous_word) + 1 == len(current_word):
4            for k in range(len(current_word)):
5                if previous_word == current_word[0:k] + current_word[k+1:]:
6                    return True
7        return False
8
9    def longestStrChain(self, words: List[str]) -> int:
10        words.sort(key=len)
11        n = len(words)
12        dp = [1 for _ in range(n)]
13        for current_word_index in range(n):
14            for previous_word_index in range(current_word_index):
15                if self.isPredecessor(words[previous_word_index], words[current_word_index]):
16                    dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1)
17        return max(dp)

JavaScript Solution

1var isPredecessor = function (previous_word, current_word) {
2  if (previous_word.length + 1 == current_word.length) {
3    for (let k = 0; k < current_word.length; k++) {
4      if (
5        previous_word ===
6        current_word.slice(0, k) + current_word.slice(k + 1)
7      )
8        return true;
9    }
10  }
11  return false;
12};
13
14/**
15 * @param {string[]} words
16 * @return {number}
17 */
18var longestStrChain = function (words) {
19  // sort words by length
20  words.sort((a, b) => a.length - b.length);
21  n = words.length;
22  dp = new Array(n).fill(1);
23
24  for (
25    let current_word_index = 0;
26    current_word_index < n;
27    current_word_index++
28  ) {
29    for (
30      let previous_word_index = 0;
31      previous_word_index < current_word_index;
32      previous_word_index++
33    ) {
34      if (
35        isPredecessor(words[previous_word_index], words[current_word_index])
36      ) {
37        dp[current_word_index] = Math.max(
38          dp[current_word_index],
39          dp[previous_word_index] + 1
40        );
41      }
42    }
43  }
44  return Math.max(...dp);
45};

$\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)$ Solutions below

C++ Solution

1class Solution {
2public:
3	int longestStrChain(vector<string> &words) {
4		// sort words by length
5		sort(words.begin(), words.end(), [](auto x, auto y) { return x.size() < y.size(); });
6		int n = words.size(), ans = 1;
7        unordered_map<string, int> dp;
8        for (auto &current_word: words) {
9            for (int j = 0; j < current_word.size(); j++) {
10                string previous_word = current_word.substr(0, j) + current_word.substr(j + 1);
11                dp[current_word] = max(dp[current_word], dp[previous_word] + 1);
12            }
13            ans = max(ans, dp[current_word]);
14        }
15		return ans;
16	}
17};

Java Solution

1class Solution {
2    public int longestStrChain(String[] words) {
3        // sort words by length
4        Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
5        int n = words.length;
6        // add padding to words so that we don't have to do s.substring(0, -1).
7        // which would throw an index out of bounds error
8        for (int i = 0; i < n; i++) {
9            words[i] = "#" + words[i];
10        }
11        TreeMap<String, Integer> dp = new TreeMap<>();
12        int ans = 1;
13        for (String current_word: words) {
14            dp.put(current_word, 1);
15            for (int j = 0; j < current_word.length(); j++) {
16                String previous_word = current_word.substring(0, j) + current_word.substring(j + 1);
17                dp.put(current_word, Math.max(dp.get(current_word), dp.getOrDefault(previous_word, 0) + 1));
18            }
19            ans = Math.max(ans, dp.get(current_word));
20        }
21        return ans;
22    }
23}

Python Solution

1class Solution:
2    def longestStrChain(self, words: List[str]) -> int:
3        # sort words by length
4        words.sort(key=len)
5        n = len(words)
6        ans = 0
7        dp = defaultdict(lambda: 0)
8        for current_word in words:
9            for j in range(len(current_word)):
10                previous_word = current_word[0:j] + current_word[j+1:]
11                dp[current_word] = max(dp[current_word], dp[previous_word] + 1)
12            ans = max(ans, dp[current_word])
13        return ans

JavaScript Solution

1/**
2 * @param {string[]} words
3 * @return {number}
4 */
5var longestStrChain = function (words) {
6  words.sort((a, b) => a.length - b.length);
7  n = words.length;
8  dp = new Map();
9  ans = 0;
10  for (current_word of words) {
11    dp[current_word] = 1;
12    for (let j = 0; j < s.length; j++) {
13      previous_word = current_word.slice(0, j) + current_word.slice(j + 1);
14      // We need (dp[previous_word] || 0) to get 0 if dp does not contain previous_word, otherwise we'd get Nan,
15      // which is larger than any integer
16      dp[current_word] = Math.max(
17        dp[current_word],
18        (dp[previous_word] || 0) + 1
19      );
20    }
21    ans = Math.max(ans, dp[current_word]);
22  }
23  return ans;
24};