DP 28. Longest Palindromic Subsequence
Вставка
- Опубліковано 10 лют 2025
- Lecture Notes/C++/Java Codes: takeuforward.o...
Problem Link: bit.ly/3pvkqUd
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/take...
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the Longest Palindromic Subsequence, please watch the LCS Dp video before solving this.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.o...
You can also get in touch with me at my social handles: linktr.ee/take...
As soon as you explained the reversing part, it clicked. Amazing video as always. Thank you very much!!!😀
Same here bro 🤜
Same here
same man
same, Striver is goated
@@sarthakvaish2520 right broo
Understood, thank you so much. It all seems to be summed up within 14 mins or so but the hard work and story behind coming up with logic such as this one, by "simply reversing the string" is always next level!
Tabulation code of LCS is very important guys...if you understand how values are getting filled in the table...you can solve this problem by yourself by thinking this problem in terms of lcs...it's the first problem of dp on strings which I have solved by myself. #Understood bhaiya❤️❤️
@अभय बिष्ट @अभय बिष्ट here, we are supposed to find the palindrome subsequence whose length is as large as possible, right !!! Now the thing is are we care about a palindromic subsequence or palindromic substring. Just think & you can see you have to figure out the palindromic string which is nothing but the subsequence of the input string. If still, the thought process didn't strike ur mind let's take an example:-
s1 = ababmna
s2 = abadbefgha
So the answer according to your thought process should be just "aba" I.e of length 3 but common subsequence of s1 & s2 ababa which is palindrome & also largest. You were just thinking of the cases where you would get a palindromic string iff it is a common substring but it is not the case every time as you can see in the above example. Hope this might help🙂🙂
will you please send the link of lcs lectuare
@StarLorD are vedya, every every substring is also subsequence, but the opposite is not always true.
@StarLorD bhai kyuki apan ko subsequence chaiye na , isliye , agar largest commom substring bolta tab second wali approach se kar dete
@tanjiroSama2020 bab is also a subsequence brother , subsequence will takecare of the substrings as well
Thankyou Striver🙏🏻❤
Before watching this video, I come up with two approaches by my own:
1) We can do this in one string recursively, starting point ==> f(n-1,0).
2) Find LCS of s and reverse(s).
**Approach 1 code c++:
class Solution {
public:
int f(int i, int j, string &s, int n, vector&dp){
if(i < 0 || j > n-1) return 0;
if(dp[i][j] != -1) return dp[i][j];
if(s[i] == s[j]) return dp[i][j] = 1 + f(i-1,j+1,s,n,dp);
else return dp[i][j] = max(f(i,j+1,s,n,dp), f(i-1,j,s,n,dp));
}
int longestPalindromeSubseq(string s) {
int n = s.length();
vectordp(n,vector(n,-1));
return f(n-1,0,s,n,dp);
}
};
**Approach 2 code c++:
class Solution {
public:
int longestCommonSubsequence(string s1, string s2) {
int n1 = s1.length(), n2 = s2.length();
vectordp(n1+1,vector(n2+1,0));
dp[0][0] = 0;
for(int i1 = 1; i1
genius brother
thought of the same thing coz it was more intuitive brother
the moment u said char at start and char at end got the idea and able to solve the que. Thanks
Did what you said in LCS tutorial "For string it is either matching or not matching" and solved it using two pointer and dp.Thank You!!!
I cant believe that after reaching to 29th video of this series , I can think DP solutions by myself and I can solve those questions, thnx alot striver bhaiya, you are doing great work
Thanks!
As soon as I saw title, approach hit my mind, thanks striver, understood !!!
I did it without watching explanation itself by the knowledge of previous videos truly thank u
Understood....Completed (28/56). HALF WAY THROUGH🙌🙌
same for me
arre bhaiya aap yaha, love ur videos
#UNDERSTOOD........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
The first problem of DP on Strings that I solved on my own. Thanks❤
Amazing. Thanks a lot for bringing up this DP series and putting hard work for a good explanation. Now DP problem look easy 😀
we can also do it by using longest common subsequence where we will start the dp by 0 to len -1 of string then if the character matches we will recursively make the i and j move close both a unit step and if not we will thereforce use left right and when i crosses j we will return
Understood
wow this is getting bigger and better with each video.....
I did this in the single String itself by recursive 2 pointer f(0, n -1). It is working great and superbb !! and also faster than the lcs(s, reverse(S)) method in this video😁😁😁😀
My goodness, who would have thought there can be such a thing which will lead to the ans of LPS...........Amazing Intuition Bhaiyaaaaaaaaaaaaa Hatssssss Offfffffff !!!
Very nice explanation sir, Thank you!
Thanks striver for explaining the reverse logic.
after watching your previous video, I can solve this question on the fly before watching this videooo.!
gazab explanation bhai , understood just in a half video
#UNDERSTOOD LCS is amazing..we can solve a lot of using that logic only...Thanks
I did this question without studying recursion from gfg, tried to make head and tail out of it using debugger, that was a nightmare, now after studying recursion I can't describe how easy this is .
Understood
Thank you Striver🙌🙌
understood striver,god may bless u for your efforts
Hey Sir!!
How do it print the longest palindromic substring.
That feeling of solving the DP question by self without watching the solution at all.
Thanks a lot, Striver. I was scared to touch the DP before :D but not anymore :) ❤
You explained the concept of longest palindromic Subsequence using LCS, that is understandable. But in some case , It does not produce output as palindrome
UNDERSTOOD...!!!
Thank you striver for the video... :)
Thanks striver❣️
Hey Striver thanks man. Great explaination. I got the gist of how to approach n solve this question the moment you said reverse here 4:27
You are amazing. Really wonderful Explanation.
Amazing explanation , thanks Striver
Problem Link : www.codingninjas.com/codestudio/problems/longest-palindromic-subsequence_842787?leftPanelTab=0
This was just simply amazing !!
understood bhaiya ❤
Here is the link to the practise problem -->> www.codingninjas.com/codestudio/problems/longest-palindromic-subsequence_842787
Thanks for sharing !!
Understood! What a fantastic explanation as always!!
Understood❤
Just after writing the second string, my mind clicked.
Thank you very much brother. Thanks a lot. Accha lagta hai jab sawal ho jata hai...
we can even reduce the time complexity by not generating a new string s2 which is reverse of s1.
Insted of this what we can do instead of s1[i-1] == s2[j-1] we can write s1[i-1] == s1[n--1-(j-1)] (also s1[n-j]) .
full code ->
int longestPalindromeSubseq(string s) {
string t;
int n = s.size();
vector dp(n+1,0);
for(int i=1; i
For those who think, the same approach will also work for the longest palindromic substring, Bro it will not work !!
For example, S = "abacdfgdcaba", S'
= "abacdgfdcaba".
The longest common substring between S and S'
is "abacd". Clearly, this is not a valid palindrome.
Do you have solution for lpsubstring
@@jayeshshrivastava5424 you can watch this video for better understanding ua-cam.com/video/WpYHNHofwjc/v-deo.html
Yes u r right
Did you get any other solution for it?
same for abcdefdefag
Understood 🙏
Striver is a good explainer .❤
thank you striver
Understood thank you striver
I came up with the solution without watching the video. Damn man, thanks !!!!!!
I solved it little differently(similar approach tho)... I used only a single string and kept one pointer(l) at 0 and the other pointer(r) at s.length()-1... then if the characters at these indexes are same and l!=r, add 2 to the answer, if l==r, add 1 to the answer... if the characters are not same, call the function twice, once with l+1,r and then with l,r-1 and take the max of the two...
class Solution
{
public int longestPalindromeSubseq(String s)
{
int dp[][] = new int[s.length()][s.length()];
for(int i = 0; i
Understood, sir. Thank you very much.
Too good explanation 😀
Amazing explanation
understood bro, thanks a lot for making this question look so simple.
Mind blowing solution
fantastic approach! I always thought that you would have to cut the string into 2 parts and find the lcs in O(n^2 * k) lol
Understood, thank you for the awesome explanation
Understood Sir
Thanks for this awesome content
Absolutely brilliant.
Understood 🎉
In a similar way if we are given to find the longest palindromic substring can we just reverse it and apply the longest common substring approach???
I tried applying the same approach it works most of the time but in some cases it does fail
If u could please explain why does that happen and put some light on it that would be really great
And keep up the good work 👏
No this approach doesn't work for longest common sub string you can try it out on leetcode, and see a solution section there they explain the reason very well hope this will help
@@adityakhare2492substring is continuous. Subsequence is there might be some letters in between
Let's take an example :- aacakdacaa
He if you say longest palindrome is aca only!
Longest palindrom subsequece is aaca ( k or d ) acaa
I hope you get the answer.
@@vengalrao5772 aaca is not a palindrome
Understand Sir, Thank you very much
This is so good ❤ now dp is easy because of you.. US ❤
Understood. Thanks for the video!
clear and perfect
understood, did this by myself.
understood ...........thanke striver
Understood, great explanation
gazabbbbbb yrrrr❤❤🔥🔥🙌🙌🙏🙏✨✨
Striver da...I found out another method....through not so much good....but still....let me share it...
I took two indices lead and lag....initialised lead to 0 and lag to the end of the string....and checked whether [lead] = s[lag] like that else lead + 1 or lag -1 ......like this...and the base case as if (lead>lag) return 0 and if (lead== lag) return 1 ....like this.....and thanks da....it was only for your dp series that i am able to come up with my own solutions ......
UNDERSTOOD!!!🔥🔥🔥🔥🔥🔥
"UNDERSTOOD BHAIYA!!"
understood Thanks raj😁
Halfway done 👍 🙌
Understood! Thanks!
Understood, thanks!
Please update the link with LPS , its actually of LCS
this is the best dp series man Understood bhaiya ❤❤
please update the problem link in the description :)
Superb Sir, Understood
Striver, I have a question: What if it was printing longest palindromic substring. The problem is for this string s = "aacakdbacaa" its inverse is string t = "aacabdkacaa". What the program is doing is taking the longest common substring which is acaa. This is not a palindrome. What is the optimal solution, please? May anyone help if they can?
Answer will be :- aaca(k or d or b ) acaa
Once check it again
We have to find longest subsequence palindrome right !
@@vengalrao5772 then please help for this substring "abcdefdefag" its reverse is "gafedfedcba" and the lcs is afdea which is not a palindrome and there's no palindrome possible other than a single char then how will this work?
"Solved without seeing the video " logic is improving day by day
Understood thank you so much
Where I can get the java code for this problem sir I cannot find in the description notes
the reversing method won't work for palindromic substring
❤❤ understood
Understood🔥🔥
Hey Striver! Can you please do a video on LC 139 . Word Break??
Understood Everything
correct the problem link
everything is excellent
Intuition is pretty basic, palindromes read back the same as left to right, i.e. in a 3 character string, character at index 1 reads the same as character at index 3, similarly 2 and 2, 1 and 3. If you reverse the original string the indices are reversed, hence you can just keep comparing from left to right to check for palindrome.
this would fail for the cases like aabadkjcabaa
what to do in that case
I was thinking this only. Where is the palindrome check? I agree that the palindromic subsequence if exists, will maintain order on reverse. But what if the palindromic subsequence does not exist at all.
Understood Sir.
Understood 🙂🙂💚
understood striver !!
Can we similarly solve Longest Palindromic Substring using finding Longest Common Substring ?
Excellent
I did this on my own 😎understood
Hi Striver, request you to kindly cover Longest Palindromic Substring. It doesn't work with the logic of Longest Common Substring. Thanks
Yes, with same logic it will fail for string="aacabdkacaa" for Longest Common Substring
@@tanujkamde3557 did you find any answer for it, getting the same test case prob