Longest String Chain - Leetcode 1048 - Python 

class Solution: def longestStrChain(self, words: List[str]) -> int: from collections import defaultdict # cache len of chain cache = defaultdict(int) # word: length of chain # initiate data data = sorted(words, key=lambda w: len(w)) for word in data: # from word, the len of chain is 1 at 1st cache[word] = 1 for index in range(len(word)): # construct predecessor predecessor = word[:index] + word[index + 1:] if predecessor in cache: cache[word] = max(cache[word], cache[predecessor] + 1) return max(cache.values())

Love The Stuff Man,Just Learning Leetcode and the way you take things that look complex and make it seem so simple is genius

Love this explanation. Thanks man. One question, I have been following the 150 Qs from neetcode and then the leetcode 150 most asked. I started Trees yesterday. Is it possible to finish up the list within a month and understand everything? (Given, I have done every topic sequentially and Continuously review 3-4 of them each day) I am really worried about my upcoming interviews. And I find the important ones(Tree, Graph, DP) quite hard😅

This is the best explanation of this problem. I couldn't come up witht this.

I don't know what to do , I was not able to think this straight even when I used hint from leetcode , But when I see some part of your solution , I was able to code it my self . I don't know where I am lagging , still not able to do many medium problems

does sorting even help us for this implementation? For the non recursive dp it helps, but for the recursive version it doesn't help since we go thru all the words anyway. can someone confirm this for me cuz im not sure lol.

from collections import defaultdict from typing import List class Solution: def longestStrChain(self, words: List[str]) -> int: words.sort(key=len) # Sort the words by length to process shorter words first word_chain = defaultdict(int) # Store the longest chain for each word for word in words: for i in range(len(word)): prev_word = word[:i] + word[i+1:] word_chain[word] = max(word_chain[word], word_chain[prev_word] + 1) return max(word_chain.values())

Love the explanation and python's string slicing

Great Explanation!!! Thanks for Daily Problem solutions!!!!

Was waiting for this ! Thanks mate

yoo appreciate the daily upload, will you ever venture into codeforces questions, etc? i know they're not really asked in interviews, but will definitely help in improving problem solving skills and are quite fun in general

i know the company in the thumbnail might not matter to you much, but TikTok has actually asked this problem more frequently (according to Leetcode stats) than any other company. So idk why Meta's logo is in the thumbnail when they've asked it very infrequently in comparison

literally was looking for a video on this yesterday, and couldnt find on, thats so weird

class Solution: def longestStrChain(self, words: List[str]) -> int: dp = {w: -1 for w in words} # {word: seqLen} def dfs(w): if w in dp: if dp[w] != -1: return dp[w] else: return 0 for i in range(len(w)): dp[w] = max(dp[w], 1 + dfs(w[:i] + w[i+1:])) return dp[w] res = 0 for i in words: res = max(res, dfs(i)) return res

For time complexity, we will not take sort into consideration?

Genius explanation 🎉

can someone explain me the line res = max(res, 1 + dfs(word_index[pred])) pls?

Waiting this explanation 🎉

isnt time complexity O(2^N * L * L * N)

Can we solve this using DSU