Longest Ideal Subsequence - Leetcode 2370 - Python

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

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

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

[@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,

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

[@goakhmad]

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.

[@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) ```

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

[@johnfusco8066]

Wow perfect timing

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

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

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

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

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

[@johnniewalkerjohnniewalker2459]

very good explanation @neetcode!!

[@DBagg-zz4ip]

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

[@mkum2141]

LCS course?

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

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

[@TF2Shows]

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

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

[@americandream1989]

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

[@chien-yuyeh9386]

So amazing! Nice tutorial🎉

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

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

[@SmoothCode]

bottom up programming is extremely painful

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

[@pastori2672]

ngl the dp solution got me like 😩

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

[@hhcdghjjgsdrt235]

I did the same as LCS but got TLE

[@CS_n00b]

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

[@devsquaaa]

Beautiful!

[@satyamjha68]

Solved it !

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

[@DeveshSoni-u6s]

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?

[@moabd7575]

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)

[@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"

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

[@deadlyecho]

A classic DP... duh !

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