Longest Palindromic Subsequence Dynamic Programming Explained with Code
Вставка
- Опубліковано 25 сер 2024
- 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
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.
Super sir 🤩🤩🤩🤩🤩🤩🤩🤩🤩🤩
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!!
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!
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.
@@Pepcoding sure sir!
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......😁
Keep learning
LPS of a string is LCS(string,reverse string) as simple as that.
bhai Gazab,
Really ? 😶😶😶
No it won't work for abcdefgdcba
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!!
No other can explain this much better than u. Really appreciate your work.
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.
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.
Ek bar mein samajh aa gaya itna clear explaination tha. Awesome video. Thanks for this
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 .
Hat off to you for making such great and detailed videos.
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😊
Best channel ever for Dynamic Programming..........👍👍
Wow!!! Brilliant explaination
The "else if" part in line no. 16 and 17 are not required. However, the explanation is really awesome. Hats off to you.
Perfect, part one explanation. I used it to create a recursion with memorization and it worked like a charm .
Really it's a very awesome video.
Very well explaintaion sir
Your video are guarantee that i will definitely get the approach..!!
Thank You Sir
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😊
Sumit sir is our jeetu bhiaya
i did it by reversing the string s1 and then perform lcs on original s1 and reversed s1.
Real DP starts from this video XD!!
there is a better approach using O(n) space, but I do appreciate your time and effort. Thanks 😃
Thank you Sir, your videos are helping me a lot to prepare for my upcoming placements.
Glad to hear that. Keep learning, Keep growing and keep loving Pepcoding!😊
Legendary Thank You................
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
For more detailed and curated content on DSA, Web Dev etc make sure to visit nados.pepcoding.com :)
🔥🔥🔥🔥
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
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 UA-cam channel as well.
The best explanation so far !!
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 )
Best explanation and your song sir
Explanation and song both are mast🤗
Glad you liked it.
For better experience sign up on nados.io
Crystal clear explanation
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
ua-cam.com/users/Pepcodingabout?view_as=subscriber
east ho ya west sumeet sir is the best
, keep motivating, keep learning and keep loving Pepcoding😊
thank you very much sir...really amazing explanation
Nice explanation sir.
Great explanation sir , maza aa gaya...
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
And you can review us here
g.page/Pepcoding/review?rc
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?
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?
Bohat sundar samjhaya master ji
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
@@Pepcoding done and thanks again for such quality content
Brilliant!
we could have done this problem by finding longest common subsequence between given string and reverse of that string.
nice
understood
Thank you Sumit Sir
Keep learning
Best !!
Glad you love the explanation, for better experience and well organised content sign up on nados.io and start learning.
perfect explanation!
Glad it was helpful!
Nice Thanks
sir, did this question by lcs method. where string s1=input_string & s2=revserse(s1);
Is it equally right?
yes
It's easier but Sumeet sir's approach is flexible. You can use it in almost all the questions which asks anything about substrings.
Longest palindrome subsequence can also be solved by taking lcs of (string s,reverse of string s)
abcdefgdcba try to solve for this and your method won't work
@@jayeshshrivastava5424 bro it's working
@@mrinmoyhalder7293 yes bro, thanks for responding.
30/79 Done
Keep going.
Sir app ko kese yeah sab pata chala sir..?
you are good singer also :)
Keep learning, Keep growing and keep loving Pepcoding!😊
the solution is for longest palindromic substring but we have to find for subsequences
Beautiful explanation.. :)
Glad you liked it
Awesome as usual...
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 )
@@Pepcoding sure sir. My pleasure.
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 )
I will post a video about performance issues of java and how they could be addressed.
@@Pepcoding sir can you share the link ,if you have made one?
Where to study gap strategy.
sir bits mein ek check divisibility by 3 ki video private aa rhi hai,
usme error hai yar, usko theik karke kal dalunga.
Bhai negative admi h Tu, ek dialogue yd agya
Too good
we can simply reverse the string and check for lcs in both the string that is reverse and actuall string is that true?
For clearing all your doubts visit on nados.pepcodin.com
nhi for eg: take abcdfgdcba
Sir in which question have you explained the gap method in detail?
2d arrays mei diagonal traversal
Concept badaliye apne sir , isse aasan bhi hai recursive approch dp me
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.
How to write the substring here? the longest substring?
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 !!!
Sir please make vide making change problem of UVA 🙏
ok ji sure.
What is UVA?
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.
Sir when to use 2D dp array?
jab question 2 parameter se define ho dp ka
Sir, we are taking LPS of abkccbc as 4.
Why don't we consider a middle element and make it 5?
beta mere hisaab se to bccb hai, aap btaie isse bda kaun sa hai?
bckcb bhi toh palindrome hua sir?
aapne characters ka order change kar dia. subsequence mei ye allowed nahi hota
Okay.. yes sir... Thank you 😊
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
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.
Hello sir jo recently webinar hua h uska video youTube p dale h yaa nhi please daal dijiye?? ??
beta college webinars upload nahi karte.
Aacha sir thanks🌹
Kya hum baat kr skte hai Aap se??
💥💥🙏🙏🙏❤
😍🥰🙏🏼
Sir Interview prep k liye offcampus cp codechef 5 6 start zruri hai kya?
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
@@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
Vhi toh bolra hu zaruri toh kch hota hi ni h, but tm zitna kroge utna cha
@@anjneykumarsingh4461 faang k liye ds algo zruri hai y to sbko pata hai ab bolo y bhi zruri nhi hai
beneficial hai bro, jaroori nahi
Dislike kon maara be. Nahi chhodega usko.
sir..it is not working for "abccccdd"
Output should be 7 but your 4
leetcode -409 😃😃😃
Check it and reply thanks 🙏🙏❤️😃
visit nados.pepcoding.com, post your doubts there community will help you out.
bhai 4 hi to hai "cccc"