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.
Dynamic Programming Solution
Let's build a chain from the shortest string to the longest string. Say we currently have the chain . We see that it doesn't matter what any of the words before are, only that there are of them. This suggests a dynamic programming solution, where the length of the longest chain that ends with the string .
First sort by increasing length. An outer loop will loop . For each , we have an inner loop to check every word before it to see if it can be a predecessor. We'll call this index . If so, we update to because we can extend the chain ending in by appending .
For example, when , , and , we find that removing from yields .
Time complexity
Let and .
Sorting takes .
Our nested loops take and call isPredecessor()
that runs in , so this part takes .
The total time complexity of this algorithm is therefore .
Space complexity
The array consumes memory.
Solutions below
C++ Solution
1class Solution {
2 public:
3 bool isPredecessor(string &previous_word, string ¤t_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};
Dynamic Programming Solution (requires HashMap)
In our last solution, checking all previous words for predecessors was slow.
Observe that each word can only have predecessors, so we can generate them all (in ) and check the best value we can get from them.
Let the length of the longest chain that ends with the string . will be a hashmap to allow for retrieval by key.
As we did before, sort by increasing length. Loop through the current string . Then for each index , let be with its th character removed. Set to . Our answer is the max of all entries in .
Time complexity
Let and .
Sorting takes .
For every string (there are of them), create each of its predecessors in and check for their value in in . This comes together to .
The total time complexity is therefore .
Space complexity
The hashmap consumes memory.
Bonus:
We can perform counting sort in , giving a total time complexity of .
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 ¤t_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};
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]
?
How does quick sort divide the problem into subproblems?
Solution Implementation
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
How does quick sort divide the problem into subproblems?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
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.