1048. Longest String Chain

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.

 

Example 1:

    Input: words = ["a","b","ba","bca","bda","bdca"]{"\n"}
    Output: 4{"\n"}
    Explanation: One of the longest word chains is ["a","
    ba","bda","bdca"].{"\n"}
  

Example 2:

    Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]{"\n"}
    Output: 5{"\n"}
    Explanation: All the words can be put in a word chain
    ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].{"\n"}
  

Example 3:

    Input: words = ["abcd","dbqca"]{"\n"}
    Output: 1{"\n"}
    Explanation: The trivial word chain ["abcd"] is one of the
    longest word chains.{"\n"}["abcd","dbqca"] is not a valid word chain because
    the ordering of the letters is changed.{"\n"}
  

 

Constraints:

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

Solution

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.

O(n2L2)\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 (w1,w2,,wk1,wk)(\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 wk\text{w}_k are, only that there are kk of them. This suggests a dynamic programming solution, where dp[i]=\text{dp}[i]= the length of the longest chain that ends with the string words[i]\text{words}[i].

First sort words\text{words} by increasing length. An outer loop will loop current_word_index\text{current\_word\_index}. For each current_word_index\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 previous_word_index\text{previous\_word\_index}. If so, we update dp[current_word_index]\text{dp}[\text{current\_word\_index}] to max(dp[current_word_index],dp[previous_word_index]+1)\max(\text{dp}[\text{current\_word\_index}], \text{dp}[\text{previous\_word\_index}]+1) because we can extend the chain ending in previous_word\text{previous\_word} by appending current_word\text{current\_word}.

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

Time complexity

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

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

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

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

Space complexity

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

O(n2L2)\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};

O(nL2)\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 O(L)\mathcal{O}(L) predecessors, so we can generate them all (in O(L2)\mathcal{O}(L^2)) and check the best dp\text{dp} value we can get from them.

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

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

Time complexity

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

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

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

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

Space complexity

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

Bonus:

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

O(nlogn+nL2)\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};

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫