No No, once ur level reaches at that point and u r in touch with these things for little longer, it starts happening that u can come up with solution. take very easier probs of DP. u will be able to make solution ur self, similarly solve most of them, move to hard DP prbs. after some solution u can solve ur self.. Tushar solved this himself or not, but he must be capable of making solutions himself.
This man should be in Matrix movie... because he solves all DP problem using matrix😂 take it as compliment bro... thank you so much for easy explanation 👍👍
Thanks Tushar.. Your videos helped me land a job in Amazon six years back. You are a very good teacher. :) Also, it will be good if you can explain top down approach at the end or the beginning. :)
@@cypherllc7297 No , just do practice as much as you can . As you'll practice a lot , your mind will automatically prepared be when you will see new dp questions. But first, you need to train your mind.
actually dont follow tushar approaches. They are bad. Who draws a dp table right away? you don't even know if its a dp problem first, you don't even know the dp formula first, you don't even know the return value first and so forth. Instead check aditya verma, andrey grehov, and mit videos for a better approach. Unless we come up with dp formula, dp questions are very hard. And for us to come up with dp formula in an interview you need to byheart a lot of patterns(a lot of people say its not needed, but this is exactly what they are doing unknowingly).
Thanks. A colleague recently send me a link to this video and asked me a couple of questions about it and DP in general. I think it would've helped if it was explained for example why you're looking at the max of 2 numbers to determine the 3rd one (the recursive nature of DP). It's only clear to someone who has solved DP problems.
Wow it's been 4 yrs but still I'll try to solve ur issue. The reason we are checking the max is because the matrix that we are building is designed in a way to give answers of subsequence of 1 lesser lenght in its adjacent spaces. And since WE NEED THE LONGEST PALINDROMIC SUBSEQUENCE HENCE we will consider the bigger one only. Although u can consider the other one and that will also lead u to some PALINDROMIC SUBSEQUENCE but it won't be the longest.
The most important thing to code a DP problem is to understand why DP needs to be implemented in the first place. Then you need to come up with a recursive approach followed by a top-down memoization approach and then you know that okay, I can do this in the bottom-up approach too. Your videos can be a whole lot better if you could explain these concepts instead of straight away jumping to bottom-up DP. I'd recommend watching Aditya Verma's DP playlist for those who'd like to understand DP thoroughly. There are some 50 videos in that playlist. And's its pure gold.
@@SHUBHAMKUMAR-xh7dk Sure.. here is one.. wcipeg.com/wiki/Longest_palindromic_subsequence#LCS-based_approach It gives wrong answer if there are multiple longest sub sequence
@@abhishekjiwankar1 nice to know, but the article you mentioned only fails when asked to find the said LPS strings. If we only care about max length of palindrome subsequence, then I guess LCS and reverse approach works fine.
Kudos to your efforts. Keep up. Ideas to some nice followups: running time, memory consumption (also considering trade-offs, we can answer just the length with O(N) memory) actual code why does this specific recursion formula work (why don't we loose by choosing greedily the matching pair)
Thank you soo much....!!! U made Dynamic Programming easy!!! Further we would expect the same for NP-Completeness problem. It is very hard to understand NPC problems and to solve them
The bottom up DP soluton also uses additional space right? I am not sure if any DP problem without memoizing and having additional memory to store past events, please correct me if m wrong.
I dont think that would work all the cases, here is an example where it wont work, 'aacdefcaa' -> here if we go by reverse and then LCS answer comes out to 3 i.e. aac or caa whereas the actual answer is 2 i.e. aa
Bro, do please explain the logic behind what you are doing and also what the rows and columns signify in the matrix. Such ridiculous time waste. We are here to learn not, to just memorize the approach. Also the recursion formula is wrong: checkout for "bebeed" or simply take "aa" it will result in 3.
bhai adita verma bol ke ek channel hae wo approch sikhata hae, uska ye wala dekh sochna kaisae hae sikhaega banda ruclips.net/video/wuOOOATz_IA/видео.html
it is simply: row index represents start index of the string. column index represents end index of the string. when you are looking at full string ie., index 0 to 5, you are getting the result of previous comparison from index 1 to 4. if the value of this is 2 , then result will be 4 + current char match result for indexes 0 and 5. hope it helps.
Here is my solution: var s = "ABBBCCCDDDAE"; var out = findLongestString(s); console.log(out); function findLongestString(str){ var lookup = {}; var max = 0; var start = 0; if(str.length == 0){ return 0; } if(str.length == 1){ return 1; } for(i = 0; i < str.length; i++){ console.log(lookup); var c = s[i]; if(lookup[c] && lookup[c] >= start){ start = lookup[c] + 1; } lookup[c] = i; max = Math.max(max, i - start + 1); } return max; } Javascript style ;). Thank you for the helpful video.
One should mention the second possible base case. If your length is 2 and first letter is the same as the last (second) letter, then you get 2 + longestPalindrom(i+1; j-1) -> so you should define: When substring start is greater than its end, longest palindrom is 0. [This is the only possibility how to bring even numbers into result.]
Great video as always. Tushar's videos really helped me to build my basic especially with dp and graphs. In the github code shared by him, he is filling every upper half cell in dp matrix. But, many times we may not need to fill all the cells. So, I think implementing it using recursion is a little faster for multiple testcases. Hope you have a good day.
@Tushar - You are directly going to solving part. But please explain how does this problem satisfies dynamic programming properties. Without that it is highly difficult to solve other problems.
Hello Tushar , there's a case where the above code throws an error, when the length is 2 and the characters MATCH, we look diagonally downwards (According to that code), which would be empty . So when L==2 && inp(i)==inp(j) T[i][j]=2;
Can't we do it like longest subsequence problem with first string as input A and second being reverse(A) - let's call it B. Here if A[i] == B[j] then dp[i][j] = dp[i-1][j-1] + 1. And if not equal then dp[i][j] = max(dp[i-1][j], dp[i][j-1]). I tried it with some examples and it works. I feel like you are essentially doing the same thing just in a more complicated manner. Please someone correct me if I am wrong in this method.
Hi sonali, It won't work.... Try this example "aacabdkacaa" reverse would be "aacakdbacaa" Common subsequence would be aacakacaa But here the answer would be "aca"
no explaination on why we choose dynamic programming and no explaination of how to think about some question ... "yes we ll use dynamic programming " is all we got
Hi Tushar, its not clear in the video why you choose to create a matrix and fill it up in a certain way. When I trace it in paper it became clear for this problem,. For example in this video I was not able to understand why the values in the left of diagonal was left empty. I like your dynamic programming videos. I have written this comment in the interest of your videos becoming clearer and getting more views.
Thank you so much for this wonderful explanation. :) Please continue to make such tutorials. Would appreciate follow up practice problems along with this.
Thanks Tushar. can we generalize the solution by initializing the matrix in T[x][x-1] = -1 in that way, when dealing with length=1 we can follow the formula, without corner case for length 1. meaning: since string[start]==string[end] T[start][end] = 2 + max[T[start+1][end], T[start][end-1]) = 2+max(-1, -1) = 1
It makes sense. Suppose you have a substring "bdb". The total length of the palindromic subsequence(ps) bdb would be the cumulative sum of ps "bd"(1, since either b or either d alone) + length of ps "db"(1 since either b or d alone) + 2(to account for the two b's at the ends of the subsequence). In the case of bdb, we are taking the 2 b's and singular d which results in a length of 3.
@@Vidur11 That doesn't make sense for input "agbdbaa". By that logic "agbdba" = 5, "gbdbaa" = 3, and "gbdba" = 3, so sum = 5 + 3 + 3 = 11 which is not the answer. The answer is supposed to be 5...
@@Alwaysiamcaesar First of all, i mentioned that the total length of the ps is equal to the total length of it's subsequent "inner" palindromic subsequences. That means you have to look inside the string recursively. In your case of "agbdbaa", we know that "bdb" has a string length of 3. Taking L=6, we see that a and a are equal so we can add these two to the palindromic subsequence. Now contained within "aa" is the subsequence "bdb" of length 3. So the total length is 3 + 2 = 5 ("abdba"). I think you are making the mistake of taking the summation of all the substrings within the given substring, when in reality you must take only the summation of the valid palindromic subsequences within a substring.
Nice Explanation ! very helpful. Thanks for uploading. If possible please upload some videos about how to approach such problems.(in short how to derive dp strategy )
The bottom up solution for this question will be 2 for loops but note that unlike the usual case , i will not start from 0 , instead from max value and towards 0
Can you explain how this would work for a input string like this 'aacdefcaa' where the answer should be 2 'aa', but i am not getting the same result with this method?
actually i think the answer should be aacdcaa since it's the longest non contiguous palindrone. It actually doesn't have to be aacdcaa it could be aacecaa or aacfcaa
According to this: en.wikipedia.org/wiki/Longest_palindromic_substring . The palindrome needs to a continous substring In the above example, g breaks the palindrome abdba. So the answer should be 'bdb'. Is that right?
This is cool, but there is a problem I noticed. Using this same algorithm, if you have repeated characters you get into some oddities. agbdba works fine, but if you have agbdbaa, the algorithm will say that position 0,5 (agbdba) will have a maximum of 5. Then when you test 0, 6, it will note that the a's are matched. agbdbaa will take the maximum of its subsequences and do 5 + 2 = 7. This is, however, incorrect.
You're right, I had an OBOB in my algorithm that led to this not working. Once I fixed it, I was able to simplify this enormously (still using Memoization, I'll go back and do dynamic programming now). Anyway, here it is: jsfiddle.net/350wsaq6/
***** Yup, but the top-down with recursion is usually referred to as using Memoization, as far as I've seen. Anyway, here is my bottom-up: jsfiddle.net/bnakbbz9/
I assume there's a small logical error in ur code in line 50. It should have been return Math.max(calculateRecursive(str, start+1, len-1), calculateRecursive(str, start, len-2)); Can you please check and verify
Is there a problem in the logic when two similar chars are present together? Consider this example input string: "AABCDB" I expect the output to be 4 (AABB) - but according to the logic presented here it says 3. Am I missing something?
here is the recurrent relation, so you can think of dp solution f(i, n) -> if Ci == Cn : 2 + f(i+1, n-1); 2 for two characters else: max( f(i+1, n), f(i, n-1) );
very confusing...i guess in this problem we need to find the existing/natural palindromic sequence from a string instead of making one by removing unwanted characters.
A small doubt :) While finding the characters that make the palindromic Sequence why do we go diaganally? I Guess Same result we can achieve if we go horizontally in backward direction and considering the character whenever the count becomes 2 less than the previous value.
Becuase we are checking string according to lenght. For example at matrix[0][0] we are checking the string[0] which is char 'a'. Hence it is not possible to do horizontally if ur still using the same technique. Whole logic needs tk be changed in a totally different way.
Hi Tushar, Your video is great. and very clear explanation. I have question about Longest Palindromic Subsequence. About Subsequence the index is not continued , so you can select from any character from the string right? I met a problem. how many Palindromic Subsequence in the string , such as string ="abac", so the Subseuence is "a" "b" "a" "c" "aa" "aa" "aba", "aca", the duplicate because the index is different the total is 8. So can this problem be solved by dp?
Can this also be done by the code for longest common subsequence? We have to find the longest common subsequence of a string S and a string S[::-1] (reverse of it) Am I right?
Best videos ever on Dynamic Programming
Can you explain how you think about such stuff. I understand how things are working but I find it hard to make up the thing myself.
Making up the thing is really hard, he probably didn't come up with it himself just saying.
No No, once ur level reaches at that point and u r in touch with these things for little longer, it starts happening that u can come up with solution.
take very easier probs of DP. u will be able to make solution ur self, similarly solve most of them, move to hard DP prbs. after some solution u can solve ur self..
Tushar solved this himself or not, but he must be capable of making solutions himself.
if you guys don't know he worked at apple, aws, amazon www.linkedin.com/in/tushar-roy-4351091a/
If you look up his solutions in GitHub, he has very clearly specified the links in the comments section at the top, to all the sites he referred.
The answer lies at 0:55 : "How do we solve this ? Yes, we will use Dynamic Programming!"
This man should be in Matrix movie... because he solves all DP problem using matrix😂 take it as compliment bro... thank you so much for easy explanation 👍👍
Thanks Tushar.. Your videos helped me land a job in Amazon six years back. You are a very good teacher. :)
Also, it will be good if you can explain top down approach at the end or the beginning. :)
I have learned whole DP from you. Trust me, this guy taught everything by just matrix.
Are you able to do new DP questions after learning from here?
@@cypherllc7297 not completely but ys i have a good idea.
@@NareshKumar-dw9xp should we memorize algorithm approach?
@@cypherllc7297 No , just do practice as much as you can . As you'll practice a lot , your mind will automatically prepared be when you will see new dp questions. But first, you need to train your mind.
actually dont follow tushar approaches. They are bad. Who draws a dp table right away? you don't even know if its a dp problem first, you don't even know the dp formula first, you don't even know the return value first and so forth.
Instead check aditya verma, andrey grehov, and mit videos for a better approach. Unless we come up with dp formula, dp questions are very hard. And for us to come up with dp formula in an interview you need to byheart a lot of patterns(a lot of people say its not needed, but this is exactly what they are doing unknowingly).
Thanks. A colleague recently send me a link to this video and asked me a couple of questions about it and DP in general. I think it would've helped if it was explained for example why you're looking at the max of 2 numbers to determine the 3rd one (the recursive nature of DP). It's only clear to someone who has solved DP problems.
Wow it's been 4 yrs but still I'll try to solve ur issue.
The reason we are checking the max is because the matrix that we are building is designed in a way to give answers of subsequence of 1 lesser lenght in its adjacent spaces. And since WE NEED THE LONGEST PALINDROMIC SUBSEQUENCE HENCE we will consider the bigger one only. Although u can consider the other one and that will also lead u to some PALINDROMIC SUBSEQUENCE but it won't be the longest.
The most important thing to code a DP problem is to understand why DP needs to be implemented in the first place. Then you need to come up with a recursive approach followed by a top-down memoization approach and then you know that okay, I can do this in the bottom-up approach too. Your videos can be a whole lot better if you could explain these concepts instead of straight away jumping to bottom-up DP.
I'd recommend watching Aditya Verma's DP playlist for those who'd like to understand DP thoroughly. There are some 50 videos in that playlist. And's its pure gold.
Better solution is, Revese the string and apply longest common subsequence between the original one and the reversed one.
there are scenario's where the reverse LCS method fails. This is better solution
@@abhishekjiwankar1 can you give a testcase for the same.
@@SHUBHAMKUMAR-xh7dk Sure.. here is one.. wcipeg.com/wiki/Longest_palindromic_subsequence#LCS-based_approach
It gives wrong answer if there are multiple longest sub sequence
@@abhishekjiwankar1 nice to know, but the article you mentioned only fails when asked to find the said LPS strings. If we only care about max length of palindrome subsequence, then I guess LCS and reverse approach works fine.
@@blasttrash that is correct
Very very nicely explained. Could you also explain a bit about the Time and Space Complexity of this algorithm.
ah, this one is tough compared to the other videos i hv seen so far
Kudos to your efforts. Keep up.
Ideas to some nice followups:
running time, memory consumption (also considering trade-offs, we can answer just the length with O(N) memory)
actual code
why does this specific recursion formula work (why don't we loose by choosing greedily the matching pair)
Thank you soo much....!!! U made Dynamic Programming easy!!!
Further we would expect the same for NP-Completeness problem. It is very hard to understand NPC problems and to solve them
one other way to solve the above problem using reverse of string and Dynamic programming (LCS)
“Here, they are same. Let’s see how it’s different.” I don’t know why but that cracked me up lol
your video never fails me down!!
Great video Tushar. Just a tip Label the matrix axis. I did my i,j the other way around and it tripped me up for a long time. Thanks
We could have taken the reverse and apply LCS to it. Is there anything wrong with that approach?
+himanshu arora
Yes you can do that and get the result in O(N^2)
epic man!! this actually works ...
The bottom up DP soluton also uses additional space right? I am not sure if any DP problem without memoizing and having additional memory to store past events, please correct me if m wrong.
I dont think that would work all the cases, here is an example where it wont work, 'aacdefcaa' -> here if we go by reverse and then LCS answer comes out to 3 i.e. aac or caa whereas the actual answer is 2 i.e. aa
@@ashwiniyengar8657 the answer would be 'aca', 'ada', 'aea', ... and so one but the longest is 3. So the answer is correct
Thanks for videos such as this. It helps a lot for self-learning.
Thanks a lot Tushar. Wonderful video. Helped a lot!!
Bro, do please explain the logic behind what you are doing and also what the rows and columns signify in the matrix. Such ridiculous time waste. We are here to learn not, to just memorize the approach.
Also the recursion formula is wrong:
checkout for "bebeed"
or simply take "aa" it will result in 3.
I guess correct part for if is
Dp[I][j]=2+dp[i+1 ][j-1]
bhai adita verma bol ke ek channel hae wo approch sikhata hae, uska ye wala dekh sochna kaisae hae sikhaega banda
ruclips.net/video/wuOOOATz_IA/видео.html
it is simply:
row index represents start index of the string. column index represents end index of the string.
when you are looking at full string ie., index 0 to 5, you are getting the result of previous comparison from index 1 to 4. if the value of this is 2 , then result will be 4 + current char match result for indexes 0 and 5.
hope it helps.
querying the longest palidromic sequence is not clear. you explained which to pick not how are they picked
You are so good man, Thank you so much for teaching us that!
Here is my solution:
var s = "ABBBCCCDDDAE";
var out = findLongestString(s);
console.log(out);
function findLongestString(str){
var lookup = {};
var max = 0;
var start = 0;
if(str.length == 0){
return 0;
}
if(str.length == 1){
return 1;
}
for(i = 0; i < str.length; i++){
console.log(lookup);
var c = s[i];
if(lookup[c] && lookup[c] >= start){
start = lookup[c] + 1;
}
lookup[c] = i;
max = Math.max(max, i - start + 1);
}
return max;
}
Javascript style ;). Thank you for the helpful video.
Clear explanation. Thanks for the sharing!
One should mention the second possible base case. If your length is 2 and first letter is the same as the last (second) letter, then you get 2 + longestPalindrom(i+1; j-1) -> so you should define: When substring start is greater than its end, longest palindrom is 0. [This is the only possibility how to bring even numbers into result.]
Great video as always. Tushar's videos really helped me to build my basic especially with dp and graphs. In the github code shared by him, he is filling every upper half cell in dp matrix. But, many times we may not need to fill all the cells. So, I think implementing it using recursion is a little faster for multiple testcases. Hope you have a good day.
Thanks, Tushar. Super clear!
I have to mute or ff whenever you try to draw or erase something. The noise was just breathtaking.
Thanks for this amazing video!
Awesome Explanation.Thanks Tushar Sir.
@Tushar - You are directly going to solving part. But please explain how does this problem satisfies dynamic programming properties. Without that it is highly difficult to solve other problems.
actually there is no need to add $ . This works just fine for even sized subsequence as well
Thanks for sharing this solution. It's quite clear!
Tushar, thank you very much for your tutorials.
Dude, I love you so much!
LPS of a string is the same as the LCS between a string and it's reverse. Same time and space complexity
Yes, I prefer this approach as well. Fewer things to remember.
I had to login to thank you. Your videos are great :)
Hello Tushar , there's a case where the above code throws an error, when the length is 2 and the characters MATCH, we look diagonally downwards (According to that code), which would be empty . So when
L==2 && inp(i)==inp(j)
T[i][j]=2;
it will not be empty but with a value of zeross the whole matrix is filled with zeros unless changed
Thank you, your explanation is very clear
You are another Sal Khan! Thanks Tushar!
Nice videos sir.
Why are you not active on RUclips since 2 years?
Your content is great.
You can just make a new string which is the reverse of the given string and find the longest common subsequence instead of this.
I also thought same approach
This may work for smaller test cases, but you will get TLE on longer strings with this approach.
Can't we do it like longest subsequence problem with first string as input A and second being reverse(A) - let's call it B. Here if A[i] == B[j] then dp[i][j] = dp[i-1][j-1] + 1. And if not equal then dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
I tried it with some examples and it works. I feel like you are essentially doing the same thing just in a more complicated manner. Please someone correct me if I am wrong in this method.
Hi sonali,
It won't work....
Try this example
"aacabdkacaa"
reverse would be
"aacakdbacaa"
Common subsequence would be
aacakacaa
But here the answer would be "aca"
no explaination on why we choose dynamic programming and no explaination of how to think about some question ... "yes we ll use dynamic programming " is all we got
Recursion with repeated data => use dynamic programming. Clear your concepts before attempting such problems.
@Harish I posted an extended comment here recently explaining how to go about thinking up the solution, before diving into the DP code! Have a look :)
Very helpful. Thx for posting video Tusar.
Hi Tushar, its not clear in the video why you choose to create a matrix and fill it up in a certain way. When I trace it in paper it became clear for this problem,. For example in this video I was not able to understand why the values in the left of diagonal was left empty. I like your dynamic programming videos. I have written this comment in the interest of your videos becoming clearer and getting more views.
I finally understood it, thx!
Thanks Tushar , great explanation
May god bless you, sir
how come bbbab is 4, for bbbb? Isn't bbabb ok too? So it is 5. Does it mean substring as in "you can delete any character"? Somewhat unclear
understands the video but couldn't understand the implementation (your code in github)
how are you calculating the dynamic array values
two for loops that you are using
anuvesh kothari Try this gist.github.com/bourneagain/fb7cc841112e24cce19c which is inline with the video explanation
should we first make the complete table before coding the problem in a competition?
Thankyou Tushar.... great... U R awesome...
Really great explanation
Brilliant explanation !
Thank you so much for this wonderful explanation. :) Please continue to make such tutorials. Would appreciate follow up practice problems along with this.
***** No. I mean suggest some problems using this concept on Online Judges like SPOJ or CodeChef for practice. :)
Tushar, You are amazing!👌
Awesome tushar!
thanks Tushar, well explained, have you participated in programming competitions?
can we extend this solution for longest palindromic substring?
very helpful. Thanks for posting the videos
How can i get the actual subsequence from this algorithm ?
Thanks Tushar.
can we generalize the solution by initializing the matrix in T[x][x-1] = -1
in that way, when dealing with length=1
we can follow the formula, without corner case for length 1. meaning:
since string[start]==string[end]
T[start][end] = 2 + max[T[start+1][end], T[start][end-1]) = 2+max(-1, -1) = 1
This makes no sense. You don't explain why we're taking the max of the two substrings of the window.
It makes sense. Suppose you have a substring "bdb". The total length of the palindromic subsequence(ps) bdb would be the cumulative sum of ps "bd"(1, since either b or either d alone) + length of ps "db"(1 since either b or d alone) + 2(to account for the two b's at the ends of the subsequence). In the case of bdb, we are taking the 2 b's and singular d which results in a length of 3.
@@Vidur11 That doesn't make sense for input "agbdbaa". By that logic "agbdba" = 5, "gbdbaa" = 3, and "gbdba" = 3, so sum = 5 + 3 + 3 = 11 which is not the answer. The answer is supposed to be 5...
@@Alwaysiamcaesar First of all, i mentioned that the total length of the ps is equal to the total length of it's subsequent "inner" palindromic subsequences. That means you have to look inside the string recursively. In your case of "agbdbaa", we know that "bdb" has a string length of 3. Taking L=6, we see that a and a are equal so we can add these two to the palindromic subsequence. Now contained within "aa" is the subsequence "bdb" of length 3. So the total length is 3 + 2 = 5 ("abdba"). I think you are making the mistake of taking the summation of all the substrings within the given substring, when in reality you must take only the summation of the valid palindromic subsequences within a substring.
You are amazing man!
Can you please share the code to print the LPS?
I think an easier approach to this would be to use the OPT function
Hello +Tushar , How to find all possible palindromic subsequence in this string ?
cool shades
this is not working for:
abcggfcab,
by what you shown the number always will be odd
It works. Maybe you made a mistake in implementation. Check it out: pastebin.com/s6Cpbv6g
Nice video. Thanks for your clear explanation. God bless you Tushar.
Nice Explanation ! very helpful. Thanks for uploading.
If possible please upload some videos about how to approach such problems.(in short how to derive dp strategy )
look really happy this day
This is pure gold
The bottom up solution for this question will be 2 for loops but note that unlike the usual case , i will not start from 0 , instead from max value and towards 0
Thank you man...That was helpful!
Can you explain how this would work for a input string like this 'aacdefcaa' where the answer should be 2 'aa', but i am not getting the same result with this method?
actually i think the answer should be aacdcaa since it's the longest non contiguous palindrone. It actually doesn't have to be aacdcaa it could be aacecaa or aacfcaa
According to this: en.wikipedia.org/wiki/Longest_palindromic_substring . The palindrome needs to a continous substring In the above example, g breaks the palindrome abdba. So the answer should be 'bdb'. Is that right?
Thanks Tushar, if someone really wants to be very good in Programming which book/s do you recommend ?
In my opinion begin with Competitive Programmer HandBook then CLRS ( *optional* ) then Competitive Programming 3 (CP3), hope it will help ^_^.
www.amazon.in/Algorithms-Unlocked-Thomas-H-Cormen/dp/0262518805/ref=as_li_ss_tl?ie=UTF8&linkCode=ll1&tag=freembastuff-21&linkId=e0c92577108ad9bec0651d4541572992
Awesome explanation!!!!
Could we run Lowest Common Subsequence with original string and reverse of original string to receive the same answer?
Yeah we can get correct result using this approach as well
This is cool, but there is a problem I noticed. Using this same algorithm, if you have repeated characters you get into some oddities.
agbdba works fine, but if you have
agbdbaa, the algorithm will say that position 0,5 (agbdba) will have a maximum of 5. Then when you test 0, 6, it will note that the a's are matched. agbdbaa will take the maximum of its subsequences and do 5 + 2 = 7. This is, however, incorrect.
You're right, I had an OBOB in my algorithm that led to this not working. Once I fixed it, I was able to simplify this enormously (still using Memoization, I'll go back and do dynamic programming now).
Anyway, here it is:
jsfiddle.net/350wsaq6/
***** Yup, but the top-down with recursion is usually referred to as using Memoization, as far as I've seen. Anyway, here is my bottom-up:
jsfiddle.net/bnakbbz9/
This is incorrect. Its an old post but still clarifying,
At 0,6 since the char matches, you would do 1,5 + 1 while will be 5 again.
I assume there's a small logical error in ur code in line 50.
It should have been
return Math.max(calculateRecursive(str, start+1, len-1), calculateRecursive(str, start, len-2));
Can you please check and verify
Is there a problem in the logic when two similar chars are present together?
Consider this example input string: "AABCDB"
I expect the output to be 4 (AABB) - but according to the logic presented here it says 3.
Am I missing something?
+algoquest Dude AABB is not a palindrome
+Ritwik Das My bad. Apologize for missing that. Excellent videos +tusharroy2525
here is the recurrent relation, so you can think of dp solution
f(i, n) -> if Ci == Cn :
2 + f(i+1, n-1); 2 for two characters
else:
max( f(i+1, n), f(i, n-1) );
Doesn't this fail for "aa"? wouldn't it it output 3?
no..it won't fail,the empty cells are ataken as zeros
Tushar, thank you!!!
very confusing...i guess in this problem we need to find the existing/natural palindromic sequence from a string instead of making one by removing unwanted characters.
A small doubt :) While finding the characters that make the palindromic Sequence why do we go diaganally? I Guess Same result we can achieve if we go horizontally in backward direction and considering the character whenever the count becomes 2 less than the previous value.
Becuase we are checking string according to lenght. For example at matrix[0][0] we are checking the string[0] which is char 'a'. Hence it is not possible to do horizontally if ur still using the same technique. Whole logic needs tk be changed in a totally different way.
So, how do we solve this problem! YES we will use Dyanamic Programming to solve this question :P
Hi Tushar,
Your video is great. and very clear explanation.
I have question about Longest Palindromic Subsequence.
About Subsequence the index is not continued , so you can select from any character from the string right?
I met a problem.
how many Palindromic Subsequence in the string , such as string ="abac", so the Subseuence is "a" "b" "a" "c" "aa" "aa" "aba", "aca", the duplicate because the index is different the total is 8.
So can this problem be solved by dp?
Great explanation 👍 thanks
Most of the time board is not visible. Good explanation!!
hw to display the new String abdba..??
yes
i guess
Can this also be done by the code for longest common subsequence?
We have to find the longest common subsequence of a string S and a string S[::-1] (reverse of it)
Am I right?
yes
So how we will solve this question?? Yes, We will use dynamic programming!
Well done bro!
can you pls make me understand the video at 7.19.....bit confusing
How do we solve this problem?
Yes. We will use dynamic programming to solve this problem.
Thanks for these videos....very helpful....:)