Longest Ideal Subsequence - Leetcode 2370

Longest Ideal Subsequence - Leetcode 2370 - Python

Рет қаралды 10,712

Күн бұрын

🚀 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

Пікірлер: 64

@omarr993 Ай бұрын

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 Ай бұрын

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 Ай бұрын

@@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 Ай бұрын

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 Ай бұрын

@@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 Ай бұрын

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)

@kamahma Ай бұрын

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.

@tinle6487 Ай бұрын

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 Ай бұрын

we're here again 🥲🥲

@suryaperiaswamy5085 Ай бұрын

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!!

@johnfusco8066 Ай бұрын

Wow perfect timing

@chien-yuyeh9386 Ай бұрын

So amazing! Nice tutorial🎉

@hamirmahal Ай бұрын

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!

@johnniewalkerjohnniewalker2459 Ай бұрын

very good explanation @neetcode!!

@rhitamdutta1996 Ай бұрын

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.

@DBagg-zz4ip Ай бұрын

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

@mkum2141 Ай бұрын

LCS course?

@AshutoshKumar-es8xy Ай бұрын

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

@devsquaaa Ай бұрын

Beautiful!

@dripcode2600 Ай бұрын

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,

@ramonsouza9846 Ай бұрын

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... 💀

@HuyLe-tu4pj Ай бұрын

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

@alexeyfv Ай бұрын

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...

@gmh14 Ай бұрын

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

@nasimnajand9697 Ай бұрын

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?

@satyamjha68 Ай бұрын

Solved it !

@heiksable Ай бұрын

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

@TF2Shows Ай бұрын

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

@TWEEDOriginal Ай бұрын

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

@americandream1989 Ай бұрын

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

@aashishbathe Ай бұрын

@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?

@ahmedtremo Ай бұрын

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

@SmoothCode Ай бұрын

bottom up programming is extremely painful

@hhcdghjjgsdrt235 Ай бұрын

I did the same as LCS but got TLE

@evgenyfedorenko953 Ай бұрын

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

@pastori2672 Ай бұрын

ngl the dp solution got me like 😩

@user-gb5id1nt8v Ай бұрын

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

@saizen3505 Ай бұрын

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?

@rafayeah1 Ай бұрын

``` 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 Ай бұрын

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

@krityaan Ай бұрын

zabcdzzklymynoypy k = 7 Pretty sure two pointers fails this

@corrogist692 Ай бұрын

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 Ай бұрын

Can you explain?

@krityaan Ай бұрын

@@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 Ай бұрын

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

@julianelmasry9556 Ай бұрын

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

@qwertythefish6442 Ай бұрын

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"

@raghuraman8829 Ай бұрын

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 Ай бұрын

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)

@deadlyecho Ай бұрын

A classic DP... duh !

@jessicakoch2331 Ай бұрын

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

@abdmo7575 Ай бұрын

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 Ай бұрын

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 Ай бұрын

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.