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};

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

A heap is a ...?


Recommended Readings

Got a question? Ask the Monster 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.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄