Leetcode 1048. Longest String Chain: Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Longest String Chain” problem.
Leetcode 1048. Longest String Chain
A naive approach would be to check every word against every other word looking for predecessors, but that would lead to a TLE result. The first important realization that we should be able to make is that while a word may have many 26 * (word.length + 1) possible successors, it can only have word.length predecessors.
So rather than iterating from small to large words and checking every combination for a link, we can store the words in a set and only check the few possible predecessors while iterating from large to small. To aid in that, we can actually separate words into an array of sets (W) indexed by word length, so that we can directly access batches of words by their length.
Leet Code : Maximum Score from Performing Multiplication Operations Cpp | Java | Python solution
(Note: As we iterate backward through W, if we find that W[i-1] is empty, we don’t need to process the words in W[i], since there cannot possibly be a predecessor match.)
Then we can use a dynamic programming (DP) approach to eliminate some common subproblems. We can define a hashmap (dp) where dp[word] is the length of the longest chain ending at word found so far.
Leetcode 1359 Count All Valid Pickup and Delivery Options (HARD)
So at each word, we’ll iterate through each of its predecessors (pred) and check the appropriate set in W for a match. If we find a match, we can update dp[pred] if dp[word] + 1 is better, increasing the chain by one. We should also separately keep track of the best chain length we’ve seen, so that once we reach the end, we can just return best.
- Time Complexity: O(N*M) .
- Space Complexity: O(N + P) .
Steps to Solve:
- 1: Input Processing
- Gather a list of strings as input.
- 2: Data Structures
- Create data structures to store string chains and their lengths.
- 3: Sort Strings
- Sort the input strings by length to process longer strings first.
- 4: Dynamic Programming
- Implement dynamic programming to find the longest string chain.
- Initialize a dictionary or map to store each string’s chain length.
- 5: Iterate Through Strings
- Iterate through the sorted strings.
- For each string, remove one character at a time and check if the resulting string is in the dictionary.
- Update the chain length for the current string.
- 6: Track the Longest Chain
- Maintain a variable to track the longest chain found.
- 7: Output
- The longest chain length is the answer.
Leet Code : longest common prefix string C++ ,java , Python Solution
C++ : Dynamic Programming
class Solution {
public:
int longestStrChain(vector<string>& words) {
vector<unordered_set<string>> W(17);
for (auto word : words)
W[word.size()].insert(word);
unordered_map<string, int> dp;
int best = 1;
for (int i = 16; i; i--) {
if (W[i-1].empty()) continue;
for (auto word : W[i]) {
int wVal = dp[word] ? dp[word] : 1;
for (int j = 0; j < word.size(); j++) {
string pred = word.substr(0,j) + word.substr(j+1);
int pVal = dp[pred] ? dp[pred] : 1;
if (W[i-1].find(pred) != W[i-1].end() && wVal >= pVal) {
dp[pred] = wVal + 1;
best = max(best, wVal + 1);
}
}
}
}
return best;
}
};Java: Dynamic Programming
import java.util.*;
class Solution {
public int longestStrChain(String[] words) {
List<Set<String>> W = new ArrayList<>(17);
for (int i = 0; i < 17; i++) {
W.add(new HashSet<>());
}
for (String word : words) {
W.get(word.length()).add(word);
}
Map<String, Integer> dp = new HashMap<>();
int best = 1;
for (int i = 16; i > 0; i--) {
if (W.get(i - 1).isEmpty()) {
continue;
}
for (String word : W.get(i)) {
int wVal = dp.getOrDefault(word, 1);
for (int j = 0; j < word.length(); j++) {
String pred = word.substring(0, j) + word.substring(j + 1);
int pVal = dp.getOrDefault(pred, 1);
if (W.get(i - 1).contains(pred) && wVal >= pVal) {
dp.put(pred, wVal + 1);
best = Math.max(best, wVal + 1);
}
}
}
}
return best;
}
}Python: Dynamic Programming
from collections import defaultdict
class Solution:
def longestStrChain(self, words):
W = [set() for _ in range(17)]
for word in words:
W[len(word)].add(word)
dp = {}
best = 1
for i in range(16, 0, -1):
if not W[i - 1]:
continue
for word in W[i]:
wVal = dp.get(word, 1)
for j in range(len(word)):
pred = word[:j] + word[j + 1:]
pVal = dp.get(pred, 1)
if pred in W[i - 1] and wVal >= pVal:
dp[pred] = wVal + 1
best = max(best, wVal + 1)
return bestJavaScript: Dynamic Programming
var longestStrChain = function(words) {
let W = Array.from({length: 17}, _ => new Set())
for (let i = 0; i < words.length; i++)
W[words[i].length].add(words[i])
let dp = new Map(), best = 1
for (let i = 16; i; i--) {
if (!W[i-1].size) continue
for (let word of W[i]) {
let wVal = dp.get(word) || 1
for (let j = 0; j < word.length; j++) {
let pred = word.slice(0,j) + word.slice(j+1)
if (W[i-1].has(pred) && wVal >= (dp.get(pred) || 1)) {
dp.set(pred, wVal + 1)
best = Math.max(best, wVal + 1)
}
}
}
}
return best
};List of Some important Leet code Question:
- Leet Code 835. Image Overlap
- Leet Code 662. maximum width of binary tree
- Leet Code 287 Find the Duplicate Number
- Leetcode 135 Candy (Hard) Solution
- Leet Code 2612 Minimum Reverse Operations
- Leet code 206 Reverse Linked List
- Leet Code 420 Strong Password Checker
- Leetcode 1359 Count All Valid Pickup and Delivery