Longest Palindromic Subsequence Dynamic Programming Explained with Code

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the problem Longest Palindromic Subsequence using dynamic programming. In this problem,
1. You are given a string str.
2. You are required to print the length of longest palindromic subsequence of string str.
To submit this problem, click here: www.pepcoding....
For a better experience and more exercises, VISIT: www.pepcoding....
#dp #dynamicprogramming #palindrome
Have a look at our result: www.pepcoding....
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education

[@Akshatved]

I have seen a lot of youtubers teach and even a lot of paid instructors teach. But I haven't seen anyone explaining DP problems so well. I hope you get all the success you deserve.

[@abhishekranjan1094]

Super sir 🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩

[@SameerShinde-14051994]

This entire video took 41 minutes from scratch to finish. In a real interview as well, this can be explained. Hats off on this explanation and clarity!!

[@harshitha4886]

41 minutes of honest Content. Your approach to question not only helps to understand the solution to question but also develops the intuition to approach questions. Thanks a lot!!

[@snehatandri8982]

Sir aap sachme gifted teacher hai... Teacher sirf vohi log bann sakte hai Jo student ke level pe jaake unko samjha paaye aur aap me ye talent hai. Thank you so much sir!

[@Pepcoding]

wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.

[@snehatandri8982]

@@Pepcoding sure sir!

[@adityaojha2701]

No other can explain this much better than u. Really appreciate your work.

[@aniket7512]

U made my day sir! U not only explained this well but in general made me realize when to use a 2-D DP table! Thank u sir!😍 I should pay u my college fees......😁

[@Pepcoding]

Keep learning

[@rushilahuja3369]

The more videos I watch, the more I start respecting you sirji ! I like the way you explain things sirji ! Massive respect for you !! Hats off and thanks for the great explanation.

[@Ballistic_Bytes]

Ek bar mein samajh aa gaya itna clear explaination tha. Awesome video. Thanks for this

[@guptapaaras]

Sir after seeing the video of "count of palindromic subeqs". I managed to do this on my own. Thank you Sir for the hard work.

[@rahulkaswan6315]

Great Explanation, I can bet that no one could explain this, better than you , after getting your explanation i never needed to see code , saved this for future reference, thanks Sumeet sir for such a wonderful video .

[@aakashyadav6228]

LPS of a string is LCS(string,reverse string) as simple as that.

[@411_danishranjan9]

bhai Gazab,

[@rajdeepghosh5556]

Really ? 😶😶😶

[@jayeshshrivastava5424]

No it won't work for abcdefgdcba

[@milindsharma2002]

Best channel ever for Dynamic Programming..........👍👍

[@amitupadhyay6511]

Perfect, part one explanation. I used it to create a recursion with memorization and it worked like a charm .

[@arpitgupta1790]

Hat off to you for making such great and detailed videos.

[@Pepcoding]

Thankyou beta! If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms ) Keep learning and keep loving Pepcoding😊

[@talentpicker]

The "else if" part in line no. 16 and 17 are not required. However, the explanation is really awesome. Hats off to you.

[@HarivanshKripaVlogs]

Your video are guarantee that i will definitely get the approach..!! Thank You Sir

[@Pepcoding]

Glad to know that you liked the content and thank you for appreciating. The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating, keep learning and keep loving Pepcoding😊

[@ayushabhishekkumar6703]

Wow!!! Brilliant explaination

[@ujjvalcodes3629]

there is a better approach using O(n) space, but I do appreciate your time and effort. Thanks 😃

[@spicyedutainment1577]

Really it's a very awesome video. Very well explaintaion sir

[@paryt7696]

This video is best for learning part, but just to solve this question I have different approach, a string is given we make b string by reversing a and then find longest common subsequence between these two strings and we got the length of longest palindromic subsequence

[@Pepcoding]

For more detailed and curated content on DSA, Web Dev etc make sure to visit nados.pepcoding.com :)

[@adityarathi3420]

🔥🔥🔥🔥

[@akashmishra5553]

Thank you Sir, your videos are helping me a lot to prepare for my upcoming placements.

[@Pepcoding]

Glad to hear that. Keep learning, Keep growing and keep loving Pepcoding!😊

[@amitjohn8845]

The best explanation so far !!

[@Pepcoding]

Glad it was helpful! and If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )

[@ashdavv]

Great way to explain the questions !!! Can you provide videos for other questions as well . I found this is the best channel to understand the questions

[@Pepcoding]

Bro, each and every questions are uploaded on nados.pepcoding.com You will find better experience, you can post your query on community tab and will find well organised content. Don't forget to subscribe our KZbin channel as well.

[@sandeshkumarchandrakar1622]

i did it by reversing the string s1 and then perform lcs on original s1 and reversed s1.

[@gouravgoel2974]

Sumit sir is our jeetu bhiaya

[@SonuKhan-mp2yn]

Legendary Thank You................

[@notinrange]

Best explanation and your song sir

[@cseengineering8582]

Explanation and song both are mast🤗

[@Pepcoding]

Glad you liked it. For better experience sign up on nados.io

[@allwell8570]

Crystal clear explanation

[@Pepcoding]

I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here kzbin.infoabout?view_as=subscriber

[@ananyaarya2465]

Real DP starts from this video XD!!

[@KundanKumar-im1gs]

thank you very much sir...really amazing explanation

[@ashwinnema06]

Nice explanation sir.

[@rahulranjan7567]

Sir yeh question toh hum count palindromic substrings ke matrix se bhi karr sakte hai. Jahan bhi True aaya hai jis cell mein udhar ki (j-i)+1 dekhte jaayenge and last mein inka max nikal denge. Won't this work?

[@411_danishranjan9]

bhaiya bas yeh bata do, DP ki size humein kaise pata chalega ki dp[ str.length() + 1 ] ki banani h ya dp[ str.length() ]; yeh dp ki size mein plus one kab lagta h , aur kab nhi?

[@arshadhussain9152]

sir, did this question by lcs method. where string s1=input_string & s2=revserse(s1); Is it equally right?

[@Pepcoding]

yes

[@rahulranjan7567]

It's easier but Sumeet sir's approach is flexible. You can use it in almost all the questions which asks anything about substrings.

[@kanishkanand1555]

Bohat sundar samjhaya master ji

[@Pepcoding]

I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like my efforts, I request a review g.page/Pepcoding/review?rc

[@kanishkanand1555]

@@Pepcoding done and thanks again for such quality content

[@sasikiran2450]

Great explanation sir , maza aa gaya...

[@Pepcoding]

You can subscribe to our channel here kzbin.infoabout?view_as=subscriber And you can review us here g.page/Pepcoding/review?rc

[@rishikeshmishra715]

Thank you Sumit Sir

[@Pepcoding]

Keep learning

[@KingSlayr]

we could have done this problem by finding longest common subsequence between given string and reverse of that string.

[@Mercer80]

nice

[@niranjanbs7549]

Nice Thanks

[@ankoor]

Brilliant!

[@iyashwantsaini]

perfect explanation!

[@Pepcoding]

Glad it was helpful!

[@nknidhi321]

Beautiful explanation.. :)

[@Pepcoding]

Glad you liked it

[@kumarakash5219]

Longest palindrome subsequence can also be solved by taking lcs of (string s,reverse of string s)

[@jayeshshrivastava5424]

abcdefgdcba try to solve for this and your method won't work

[@mrinmoyhalder7293]

@@jayeshshrivastava5424 bro it's working

[@jayeshshrivastava5424]

@@mrinmoyhalder7293 yes bro, thanks for responding.

[@Rahul-bl6rv]

sir my question in java get TLE But the same code in C++ get accepted What will i do for it to make java function is faster ( like out of 30% Question this situation occurs )

[@Pepcoding]

I will post a video about performance issues of java and how they could be addressed.

[@mickyman753]

@@Pepcoding sir can you share the link ,if you have made one?

[@wecan2729]

we can simply reverse the string and check for lcs in both the string that is reverse and actuall string is that true?

[@Pepcoding]

For clearing all your doubts visit on nados.pepcodin.com

[@RAHUL-gf3ft]

nhi for eg: take abcdfgdcba

[@factswithai2]

east ho ya west sumeet sir is the best

[@Pepcoding]

, keep motivating, keep learning and keep loving Pepcoding😊

[@jatinkumar4410]

Awesome as usual...

[@Pepcoding]

Thanks buddy! If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )

[@jatinkumar4410]

@@Pepcoding sure sir. My pleasure.

[@arvindsinha1566]

you are good singer also :)

[@Pepcoding]

Keep learning, Keep growing and keep loving Pepcoding!😊

[@tanishkumar6682]

understood

[@KB-zg8ho]

Sir in which question have you explained the gap method in detail?

[@Pepcoding]

2d arrays mei diagonal traversal

[@NaveenSharma-pc5ej]

Sir please make vide making change problem of UVA 🙏

[@Pepcoding]

ok ji sure.

[@abhinavgarg7654]

What is UVA?

[@abhayyadav1468]

Hello sir jo recently webinar hua h uska video youTube p dale h yaa nhi please daal dijiye?? ??

[@Pepcoding]

beta college webinars upload nahi karte.

[@abhayyadav1468]

Aacha sir thanks🌹

[@abhayyadav1468]

Kya hum baat kr skte hai Aap se??

[@ayushgoel9584]

sir bits mein ek check divisibility by 3 ki video private aa rhi hai,

[@Pepcoding]

usme error hai yar, usko theik karke kal dalunga.

[@anjneykumarsingh4461]

Bhai negative admi h Tu, ek dialogue yd agya

[@bismeetsingh352]

Where to study gap strategy.

[@manishkumarsingh4631]

30/79 Done

[@Pepcoding]

Keep going.

[@shachisharma8045]

Sir, we are taking LPS of abkccbc as 4. Why don't we consider a middle element and make it 5?

[@Pepcoding]

beta mere hisaab se to bccb hai, aap btaie isse bda kaun sa hai?

[@shachisharma8045]

bckcb bhi toh palindrome hua sir?

[@Pepcoding]

aapne characters ka order change kar dia. subsequence mei ye allowed nahi hota

[@shachisharma8045]

Okay.. yes sir... Thank you 😊

[@ArcGaming07YT]

the solution is for longest palindromic substring but we have to find for subsequences

[@democratcobra]

Sir app ko kese yeah sab pata chala sir..?

[@vivekkumarsingh7172]

Too good

[@nuamaaniqbal6373]

Best !!

[@Pepcoding]

Glad you love the explanation, for better experience and well organised content sign up on nados.io and start learning.

[@cartube6219]

Concept badaliye apne sir , isse aasan bhi hai recursive approch dp me

[@Pepcoding]

java ki recursion wali DP hackerrank pe test case pass nahi karti, stack bhar jati hai. Sirf tabulation wali he chalti hai. (If you want to check try sherlock and cost question on hackerrank to know why it is necessary for java programmers to do DP via tabulation) C++ mei dono chal jati hain.

[@PankajKP]

Sir Interview prep k liye offcampus cp codechef 5 6 start zruri hai kya?

[@anjneykumarsingh4461]

Bhai sir k famous dialogue h, zaroori toh duniya m bhut kch ni h, amazon microsoft jaana zaruri h , Tu bata space p jana jruri tha kya

[@PankajKP]

@@anjneykumarsingh4461 bhai tum kuch or matlb nikal rhe ho. On campus to zruri nhi h ye to muje pata hai but offcampus resume shortlist nhi hota kahi bhi to kuch mediocre jaisa lgta hai har kisi k pas 6 star

[@anjneykumarsingh4461]

Vhi toh bolra hu zaruri toh kch hota hi ni h, but tm zitna kroge utna cha

[@PankajKP]

@@anjneykumarsingh4461 faang k liye ds algo zruri hai y to sbko pata hai ab bolo y bhi zruri nhi hai

[@Pepcoding]

beneficial hai bro, jaroori nahi

[@vijaynaryansingh8401]

Sir khud se etna soch pana bahut msukil sa hai kaise soche sir previous pattern per based nhi tha ye but sir esme soche kaise

[@Pepcoding]

Beta, jab aise he solutions dekh dekh kr aur practise kr k 300-400 svaal kr loge, to apne aap thinking capability bd jayegi aur khud se soch paoge fr aap khud he approach.

[@ashutoshjha5356]

sir, by this method we can get the length of all the substrings but not subsequence, because in longest palindromic substring you are using same technique.

[@mehulmulchandani8126]

Sir when to use 2D dp array?

[@Pepcoding]

jab question 2 parameter se define ho dp ka

[@nehaagrawal670]

How to write the substring here? the longest substring?

[@AshutoshKumar-oo3hc]

The pattern that I have notices so far is that => { subsequence == substring + you can leave the elements in-between but cannot mess the order }. To find the substring, maintain a 2-D dp array of boolean type and also have a global values of your start index and end index of your substring with global max_size of substring. Once you encounter a substring that has size greater than your global max_size, then update your start index and end index with new values of i and j. This way you can return the ans. But whenever we encounter the problem around subsequence we tend to use Integer [ ][ ]DP. The idea remains same but the matrix now has the changed meaning. Each box tend to store the maximum possible till that box. Printing the largest palindromic subsequence is not possible without actually performing additional tasks. I hope this helps anyone. Cheers !!!

[@indranilchakraborty5949]

💥💥🙏🙏🙏❤

[@Pepcoding]

😍🥰🙏🏼

[@trading.helper-1997]

Dislike kon maara be. Nahi chhodega usko.

[@abhishekranjan1094]

sir..it is not working for "abccccdd" Output should be 7 but your 4 leetcode -409 😃😃😃 Check it and reply thanks 🙏🙏❤️😃

[@Pepcoding]

visit nados.pepcoding.com, post your doubts there community will help you out.

[@RAHUL-gf3ft]

bhai 4 hi to hai "cccc"