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.
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. :)
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.
@@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)
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 👍👍
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 ua-cam.com/video/wuOOOATz_IA/v-deo.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.
@@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).
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.
@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.
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
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
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;
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.
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. 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.
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.]
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'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"
LANGUAGE USED IS JAVA class Solution {static int z1[]=new int[100]; static int z=0; static String q[]=new String [100]; public static void main(String[] args) { String ss="anuragnitinrotavatorsindhuracecar"; int n=ss.length(); char s[]=new char[100]; s=ss.toCharArray(); for (int i=0;i
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
Thank you so much for this wonderful explanation. :) Please continue to make such tutorials. Would appreciate follow up practice problems along with this.
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
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
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?
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.
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 )
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) );
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?
i know writing algorithms for solving these kind of questions are pretty tough without proper practice. Tushar, can you please suggest me any site to practice on basic to advance programming?
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?
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
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!"
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. :)
Best videos ever on Dynamic Programming
Very very nicely explained. Could you also explain a bit about the Time and Space Complexity of this algorithm.
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.
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
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)
querying the longest palidromic sequence is not clear. you explained which to pick not how are they picked
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 👍👍
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
ua-cam.com/video/wuOOOATz_IA/v-deo.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.
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
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).
ah, this one is tough compared to the other videos i hv seen so far
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.
@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.
“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!!
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
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
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
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.
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.
I finally understood it, thx!
I have to mute or ff whenever you try to draw or erase something. The noise was just breathtaking.
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
Thanks for this amazing video!
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.
Clear explanation. Thanks for the sharing!
Thanks a lot Tushar. Wonderful video. Helped a lot!!
thanks Tushar, well explained, have you participated in programming competitions?
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.]
Thanks for videos such as this. It helps a lot for self-learning.
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.
Thanks, Tushar. Super clear!
You are so good man, Thank you so much for teaching us that!
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
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'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"
Awesome Explanation.Thanks Tushar Sir.
You are amazing man!
Thank you so much!
Really great explanation
LANGUAGE USED IS JAVA
class Solution {static int z1[]=new int[100];
static int z=0;
static String q[]=new String [100];
public static void main(String[] args) {
String ss="anuragnitinrotavatorsindhuracecar";
int n=ss.length();
char s[]=new char[100];
s=ss.toCharArray();
for (int i=0;i
Nice videos sir.
Why are you not active on UA-cam since 2 years?
Your content is great.
Thanks for sharing this solution. It's quite clear!
actually there is no need to add $ . This works just fine for even sized subsequence as well
May god bless you, sir
Tushar, thank you very much for your tutorials.
can we extend this solution for longest palindromic substring?
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 :)
I had to login to thank you. Your videos are great :)
Thank you, your explanation is very clear
Dude, I love you so much!
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.
Very helpful. Thx for posting video Tusar.
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
should we first make the complete table before coding the problem in a competition?
How can i get the actual subsequence from this algorithm ?
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. :)
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
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
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
This is pure gold
Thanks Tushar , great explanation
Brilliant explanation !
Hello +Tushar , How to find all possible palindromic subsequence in this string ?
You are another Sal Khan! Thanks Tushar!
cool shades
very helpful. Thanks for posting the videos
How do we solve this problem?
Yes. We will use dynamic programming to solve this problem.
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?
Thankyou Tushar.... great... U R awesome...
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
one other way to solve the above problem using reverse of string and Dynamic programming (LCS)
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.
Awesome explanation!!!!
amazing !
Tushar, You are amazing!👌
Awesome tushar!
can you pls make me understand the video at 7.19.....bit confusing
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 )
Do you initialize len 1, 2 and 3 entries first and then calculate others based on that
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
Thank you man...That was helpful!
I think an easier approach to this would be to use the OPT function
Tushar, thank you!!!
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
look really happy this day
i know writing algorithms for solving these kind of questions are pretty tough without proper practice. Tushar, can you please suggest me any site to practice on basic to advance programming?
www.interviewbit.com
if i'm not mistake
space complexity = n^2
time complexity = n(n+1)/2, the formula of sum first n numbers
Thanks for these videos....very helpful....:)
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
Great explanation 👍 thanks
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
very well explained.
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
Thank you!
Can you please share the code to print the LPS?