DP 28. Longest Palindromic Subsequence

Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
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/takeUforward
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.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward

[@johncenakiwi]

As soon as you explained the reversing part, it clicked. Amazing video as always. Thank you very much!!!😀

[@sarthakvaish2520]

Same here bro 🤜

[@iEntertainmentFunShorts]

Same here

[@lakshsinghania]

same man

[@fustigate8933]

same, Striver is goated

[@PiyushSharma-ud9qk]

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❤️❤️

[@sdexstarlord]

bro agr
s1 = "bbabcd"
s2 = "dcbabb"
dono me "bab" common h to vo largest common substring se solve hoga na ??
to bhaiya ne largest common subsequence q bola h ??

[@PiyushSharma-ud9qk]

@@sdexstarlord @अभय बिष्ट 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🙂🙂

[@sankaranarayanankm7049]

will you please send the link of lcs lectuare

[@sandeepmourya8922]

@@sdexstarlord are vedya, every every substring is also subsequence, but the opposite is not always true.

[@pulkitjain5159]

@@sdexstarlord bhai kyuki apan ko subsequence chaiye na , isliye , agar largest commom substring bolta tab second wali approach se kar dete

[@Harshit126]

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!

[@JeevanGaikwad-G1]

Amazing. Thanks a lot for bringing up this DP series and putting hard work for a good explanation. Now DP problem look easy 😀

[@anubhav_gupta_]

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

[@mayank_singh_43]

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

[@sachinkore974]

the moment u said char at start and char at end got the idea and able to solve the que. Thanks

[@dorisalarushika5460]

I did it without watching explanation itself by the knowledge of previous videos truly thank u

[@hetavvakani7025]

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

[@jaaswindkotian6615]

This was just simply amazing !!

[@ranasauravsingh]

UNDERSTOOD...!!!
Thank you striver for the video... :)

[@kathanvakharia]

Understood....Completed (28/56). HALF WAY THROUGH🙌🙌

[@narendrakumariitb]

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

[@cinime]

Understood! What a fantastic explanation as always!!

[@dipaligangawane980]

You are amazing. Really wonderful Explanation.

[@undergrad4980]

Absolutely brilliant.

[@shreyasnagabhushan4918]

understood bro, thanks a lot for making this question look so simple.

[@radharamamohanakunnattur3035]

Understood, thank you for the awesome explanation

[@raj_kundalia]

Understood. Thanks for the video!

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@warriorgaming9509]

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

[@gsampath8017]

Thanks striver❣️

[@gaura-krishna]

Thank you very much brother. Thanks a lot. Accha lagta hai jab sawal ho jata hai...

[@andreasleonidou3620]

Understood! Thanks!

[@ritikshandilya7075]

Amazing explanation , thanks Striver

[@AlokLaha-te2pd]

Thanks striver for explaining the reverse logic.

[@prajwal8458]

Correct Problem link: www.codingninjas.com/codestudio/problems/longest-palindromic-subsequence_842787

[@piyushsaxena7399]

thanks

[@chitreshmourya-sz6kb]

gazab explanation bhai , understood just in a half video

[@030-sham]

thank you striver

[@VishalYadav-gk1kg]

Very nice explanation sir, Thank you!

[@nguyengiahuy6292]

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

[@rishabhagarwal8049]

Understand Sir, Thank you very much

[@varunaggarwal7126]

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 .

[@koocheukkeijacky9704]

after watching your previous video, I can solve this question on the fly before watching this videooo.!

[@stith_pragya]

#UNDERSTOOD........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@lakshaysharma6550]

UNDERSTOOD!!!🔥🔥🔥🔥🔥🔥

[@himanshuagrawal8012]

#UNDERSTOOD LCS is amazing..we can solve a lot of using that logic only...Thanks

[@ssc_-kn6os]

Problem Link : www.codingninjas.com/codestudio/problems/longest-palindromic-subsequence_842787?leftPanelTab=0

[@AbhishekGupta-xz1gd]

Understood, great explanation

[@akashkumarsingh3595]

Understood🔥🔥

[@DevashishJose]

Understood thank you so much

[@vijayvardhan2698]

I came up with the solution without watching the video. Damn man, thanks !!!!!!

[@shubhankar_naik]

Mind blowing solution

[@VishalPatel_imvishal]

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

[@saimhatre89]

Superb Sir, Understood

[@enigma2777]

Amazing. understood

[@amishasahu1586]

Hey Sir!!
How do it print the longest palindromic substring.

[@arnabroy2995]

This is so good ❤ now dp is easy because of you.. US ❤

[@johncenakiwi]

Hey Striver! Can you please do a video on LC 139 . Word Break??

[@siddhantvishnu4309]

Amazing!!!

[@kartikrameshchavan6662]

Understood 🙏

[@ayushgautam169]

understood striver !!

[@shivangsaini3940]

understood bhaiya ❤

[@soniamalik4929]

Understood Sir

[@deepakjain4481]

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

[@abdallaalhag4425]

understood Thanks raj😁

[@pavan_talluri6540]

Thanks!

[@parshchoradia9909]

Understood Sir!

[@vaishnavithakur6460]

Understood!!!

[@Hello-ro6hr]

UNDERSTOOD ...

[@theresilientpianist7114]

gazabbbbbb yrrrr❤❤🔥🔥🙌🙌🙏🙏✨✨

[@mantrarajgotecha3055]

Understood !!

[@harshitjaiswal9439]

Understood!

[@chanchalroy3417]

Halfway done 👍 🙌

[@shubhigupta5689]

Understood🌻

[@adarshkumar167]

Just after writing the second string, my mind clicked.

[@himanshuagrawal8012]

Please update the link with LPS , its actually of LCS

[@vipulaggarwal7489]

understood!

[@VikashYadav-px8ei]

Understood 🎉

[@saurabhrthakur]

UNDERSTOOD!

[@sujalgupta6100]

Understood.

[@adebisisheriff159]

Understood bro!!

[@pulkitchausali1354]

"Solved without seeing the video " logic is improving day by day

[@sanamdeepsingh7914]

understood bhaiya

[@varnitgupta706]

UNDERSTOOD

[@ishanminhas4676]

so good

[@yeswanthh5068]

Understood 🙂🙂💚

[@shauryamalik7519]

understood very well, but what to do if I have to return the Longest Palindromic Substring and not the length

[@Whyush7]

please update the problem link in the description :)

[@pratyakshsaxena7420]

Understood ❤

[@chitranshjain5075]

Understood. 🤟🏻

[@prabhakaran5542]

Understood❤

[@arihantjammar8888]

Understood 😊

[@udatyadeb101]

understood, did this by myself.

[@aditithakur6226]

Understood Sir.

[@satyampande684]

understood!!

[@fettuccine794]

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😁😁😁😀

[@mahir_labib]

mind blown

[@_hulk748]

understood sir🙏🙏❤️❤️

[@bhushanmilindborole9616]

Mindblown bhai 🔥

[@amansamal8233]

❤❤ understood

[@Ajay-ei2jo]

Understood👍

[@rahulrrahulr2151]

Where I can get the java code for this problem sir I cannot find in the description notes

[@piyush2750]

How could we print the longest pallindromic substring . I'm able to generate the correct dp array.I could get the max value also from dp array

[@bhuoneparmar5098]

this is the best dp series man Understood bhaiya ❤❤

[@priyanshvatsal9791]

Understood 🥰

[@75dhruvkhanna71]

the reversing method won't work for palindromic substring

[@Nitro-kx7ok]

Understood sir🙏❤🙇‍♂

[@adityasaxena6971]

Understood Sirr

[@UECAbhishekKumar]

Understood