# Leet Code 1048. Longest String Chain (Medium)

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

leet Code 392. Is Subsequence (easy)

### 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++) {
}

for (String word : words) {
}

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

Leet Code 226. Invert Binary Tree (Easy)

### Python: Dynamic Programming

``````from collections import defaultdict

class Solution:
def longestStrChain(self, words):
W = [set() for _ in range(17)]

for word in words:

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 best``````

Leet Code 1658. Minimum Operations to Reduce X to Zero

### JavaScript: Dynamic Programming

``````var longestStrChain = function(words) {
let W = Array.from({length: 17}, _ => new Set())
for (let i = 0; i < words.length; 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: I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.