Longest String Chain - Leetcode 1048 - Python

Solving Leetcode 1048, longest string chain, todays daily leetcode problem on september 22.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/longest...
0:00 - Read the problem
0:30 - Drawing Explanation
6:12 - Coding Explanation
13:57 - Time / Space
leetcode 1048
#neetcode #leetcode #python

[@troytaylor4719]

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

[@danielsun716]

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())

[@iscoto4914]

I think he makes it complex. You're one is Good. Good work

[@gauthamsakthiveeran7946]

Was waiting for this ! Thanks mate

[@bidishadas832]

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

[@vs3.14]

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😅

[@aasheesh6001]

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

[@michelle_tsai_drums]

Love the explanation and python's string slicing

[@VidyaBhandary]

Genius explanation 🎉

[@devkumar9889]

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

[@reggiehurley1479]

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.

[@shrn]

On second thought, it doesn't help actually. You are right

[@rajanmaheshwari]

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

[@user-hm8pj7mi7f]

Waiting this explanation 🎉

[@iscoto4914]

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

[@phpostrich]

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

[@phpostrich]

thanks for the help :)

[@roywastaken]

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

[@saiashishvure]

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

[@iscoto4914]

codeforces not worth it unless u're targeting for icpc and you have enough time in hand

[@saiashishvure]

@@iscoto4914 basically expand out from interview prep to problem solving in general. or atleast maybe once in a while

[@AchyutSarmaB]

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())

[@Raymond-Wu]

This was easier to understand for me than the solution shown in the video. Great job!

[@uddiptakalita3006]

Can we solve this using DSU

[@sumitsharma6738]

Yeah, my First thought is also Trie or DSU but the answer is noo once you try to draw the trie you will see why DSU will not work