Longest Ideal Subsequence - Leetcode 2370 - Python

Подписаться 145 тыс.

Просмотров 11 тыс.

50% 1

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/longest...
0:00 - Read the problem
0:30 - Drawing Recursive
8:25 - Coding Recursive
14:28 - Drawing Optimal
24:43 - Coding Optimal
leetcode 2370
#neetcode #leetcode #python

Опубликовано:

9 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 65

@omarr993 2 месяца назад

ngl i didn't get the bottom up approach explanation at all, I think it would probably be better to show the entire filled up grid of values for beginners to understand

@NeetCodeIO 2 месяца назад

Yeah the only reason I didn't is because I feel this video is long enough, I'm not sure if people would want the video to even longer but I could be wrong.

@omarr993 2 месяца назад

@@NeetCodeIO can potentially do another dp problem video similar to this and instead of spending time explaining top down, you can do in depth bottom up approach?

@xingyuxiang1637 2 месяца назад

I am confused when it says that bottom-up and top-down dp are different. This one is like the Minimum Height Trees problem, if one does not use topological sort simply run bfs on every leaf node, then it shows TLE because counting the number of edges reduces the amount of nodes visited by changing the way of visiting the graph. But is not it O(m * N) is O(N) if m is small? This improvement of space may be based on some concepts similar to the topological sort that has not been mentioned yet.

@ik6071 2 месяца назад

@@NeetCodeIO i was not able to understand the bottom up approach. if you could write it in a medium post or a longer video or any other explanation, id be grateful

@ik6071 2 месяца назад

i am going to write my thoughts on tring to comprehend it, the dp is supposed to be len(string)*26 (for every single letter ? im thinking thats what the prev would be so that column would be 1... im not sure)

@tinle6487 2 месяца назад

This problem is kind of strange to me that normally I only able to come up with the recursion dp and have a hard time to do bottom up version, but in this case, I came up with the bottom up first

@HuyLe-tu4pj 2 месяца назад

we're here again 🥲🥲

@rhitamdutta1996 2 месяца назад

In my opinion the dfs approach was relatively simple and could have been avoided. It sucks that the dp approach was rushed, I had to look up other sources to understand it perfectly. I am used to Neet doing a top down approach, this bottom up did not make sense to me at all.

@ramonsouza9846 2 месяца назад

This one was really hard for me... I almost wished I could use dynamic escalation to buy more RAM and have my brute force 48gb hashset pass instead of having to use dynamic programing... 💀

@kamahma 2 месяца назад

Hi Neet. Thank you for leaving us some room to think about the problem, to draw it and try to visualize it! This was very helpful explanation video.

@nasimnajand9697 2 месяца назад

Thanks in advance but I have a question. why in bottom-up way we track all valid chars that have the suitable diff and we do not track the last char that made vali longest subsequence?

@johnfusco8066 2 месяца назад

Wow perfect timing

@suryaperiaswamy5085 2 месяца назад

One thing to note is that the recursive solution passes if you use c++ and a 2d array for caching instead of python with hashmap. Great video!!

@gmh14 2 месяца назад

Idk but I prefer bottom up, aka reversed so at least we don't change our entire intuition of the problem (e.g. now longest string ENDING at idx) just for the sake of iterating from 0 to n instead of n to 0 lol

@TF2Shows 2 месяца назад

Can someone explain whats the running complexity and memory complexity of both solutions? Im so confused

@dripcode2600 2 месяца назад

start with the first letter and see if there's another letter within 2 letters of it. if not drop it, if so grab that letter and put the current letter into an array. repeat process until there's no more letters. the length of the array with all the letters stored in it is your answer,

@AshutoshKumar-es8xy 2 месяца назад

Its just LIS with 26 alphabet hack We were checking previous indexes' best and adding a one to it in LIS but here we can just iterate through all the abs diff

@aashishbathe 2 месяца назад

@NeetCodeIO Hey, I didnt understand why caching was even needed in first solution. Like the same (i, prev) can never occur again right? Coz we are always increasing i? Can anyone please explain that?

@HuyLe-tu4pj 2 месяца назад

I understand your first solution but I have a trouble with the second

@chien-yuyeh9386 2 месяца назад

So amazing! Nice tutorial🎉

@devsquaaa 2 месяца назад

Beautiful!

@ahmedtremo 2 месяца назад

Why are setting dp[cur] = max(dp[cur], longest), I think we are only computing it once so we don't need the max function

@americandream1989 2 месяца назад

Damn, every time I watched your video, I feel this guy is way more smarter than me. Damn!

@heiksable 2 месяца назад

it never states anywhere in the problem description that the characters in the input string are unique, right? so the 2nd solution wouldn't work in that case since it assumes this

@hamirmahal 2 месяца назад

To echo some other comments, seeing more of the table filled in could be instructive. It might be useful to make "spinoff" videos that cover parts of the main video in more detail? This video was really helpful overall. Thanks for posting it!

@pastori2672 2 месяца назад

ngl the dp solution got me like 😩

@evgenyfedorenko953 2 месяца назад

Why in top down solution Time complexity is O(n*26)? Isn't it O(n*n)? Even though we use a char as the value for the second index in the two dimensional array we still iterate it n*n times

@DBagg-zz4ip 2 месяца назад

Whew. Gonna put this one on hold until I do the LCS course.

@mkum2141 2 месяца назад

LCS course?

@johnniewalkerjohnniewalker2459 2 месяца назад

very good explanation @neetcode!!

@SmoothCode 2 месяца назад

bottom up programming is extremely painful

@satyamjha68 2 месяца назад

Solved it !

@TWEEDOriginal 2 месяца назад

JS solution using an object. var longestIdealString = function (s, k) { let res = 1 const dp = {} dp[s[0]] = 1 //loop through string for (let i = 1; i < s.length; i++) { let temp = 1 //compare with previous letters in dp obj for (const [key, value] of Object.entries(dp)) { if (Math.abs(s.charCodeAt(i) - key.charCodeAt(0))

@alexeyfv 2 месяца назад

Thanks for your videos. Idk why, but DP is super hard for me. I can see this pattern when I read the problem description, but I can spend hours trying to find the solution...

@hhcdghjjgsdrt235 2 месяца назад

I did the same as LCS but got TLE

@saizen3505 2 месяца назад

In the recursive solution why are we passing the character??? Instead we can pass the prev index, (i did that but got wrong answer) Can anybody explain this?

@CS_n00b 27 дней назад

i preder the traditional backwards dp approach not the way you say you do to help people understand.

@user-gb5id1nt8v 2 месяца назад

i did not get the last solution coz i am not so good in dp rn. But i will try again

@rafayeah1 2 месяца назад

``` python class Solution: def longestIdealString(self, s: str, k: int) -> int: dp = [0] * 26 for c in s: curr = ord(c) - ord("a") dp[curr] = max(dp[max(0, curr-k):min(curr+k+1, 26)]) + 1 return max(dp) ```

@comatosesperrow 2 месяца назад

Couldn't you also use a two pointer approach for O(n) time and O(n) memory?

@krityaan 2 месяца назад

zabcdzzklymynoypy k = 7 Pretty sure two pointers fails this

@julianelmasry9556 2 месяца назад

I still do not understand why we need to do the skip case first. Can anyone explain?

@qwertythefish6442 2 месяца назад

What is the longest subsequence for this test case? "pvjcci" Answer: 2 -> "cc" If you don't skip the longest sequence will just be "p"

@corrogist692 2 месяца назад

further optimized runtime: ``` dp = [0] * 51 for c in s: curr = ord(c)-72 dp[curr] = max(dp[curr - k : curr + k + 1]) + 1 return max(dp) ```

@omkarnag24 2 месяца назад

Can you explain?

@krityaan 2 месяца назад

@@omkarnag24it's not further optimised. Max(dp[curr-k:curr + k + 1]) is O(n) It's just writing the same solution in lesser lines

@corrogist692 2 месяца назад

yea true, just basically skipped the absolute value part and the runtime improved

@deadlyecho 2 месяца назад

A classic DP... duh !

@jessicakoch2331 2 месяца назад

honestly, sometimes I am going through these dp videos and i still dont get it, waiting for that light bulb to go off. Currently, not sure it is even flickering LOL

@raghuraman8829 2 месяца назад

why not use stack and check peek and curr char diff and add in stack and finally returning stack size ??? (breaks few testcases) class Solution { var stack = Stack() fun longestIdealString(s: String, k: Int): Int { s.forEach{ char -> if( stack.isEmpty() || (stack.peek() - char)

@raghuraman8829 2 месяца назад

caz , imagine a case like a,b,x,y,x and k = 1. this fails for my code with solution 2 (a,b will be in my stack ) rather than 3 (x,y,z)

@abdmo7575 2 месяца назад

i used a 2d vector with c++ and yet i got a TLE just like you here is my solution if someone is interested: class Solution { public: int longestIdealString(string s, int k) { int n = s.size(); vector dp(n, vector(26,-1)); function dfs = [&](int i, int prev){ if(i == n) return 0; if(prev != -1 && dp[i][prev] != -1) return dp[i][prev]; int res = dfs(i+1, prev); int curr = s[i] - 'a'; if(abs(curr - prev)

@homyakMilashka 2 месяца назад

Yep, the table is confusing, I guess everyone who watches your videos often can allready write a decision tree in their sleep, the non-decision tree approach should really be explained in more detail. Please =)))

@supremoluminary 2 месяца назад

Around 11 minutes 20 seconds, “now you can see why I put the skip case before” No, I can’t see why you put the skip case before. I do not understand the explanation. My approach to thinking through this problem was completely different. I wasn’t able to solve it on my own. Your explanation eludes me. I think the explanation about the ord function in python is not only unnecessary, but a distraction from understanding the key concepts of your solution. Thank you.