26 Longest Palindromic Subsequence
Вставка
- Опубліковано 12 вер 2024
- Longest Palindromic Subsequence
Given a sequence, find the length of the longest palindromic subsequence in it.
Example :
Input:"bbbab"
Output:4
PROBLEM STATEMENT LINK:www.geeksforge...
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
This playlist is one of the rarest gem in youtube.
gem which is yet to be found by many coders!
leetcode.com/problems/maximize-palindrome-length-from-subsequences/ using this idea doesn't work always, this question is a example.(I mean it makes things harder)
@@Prashantkumar-pn6qq tere jaise bache coders ke liye ye playlist chahiye
@@pr1493 kyu bro... Tereko kya lagta hai yeh DP playlist acha nahi h?
@@thegreekgoat98 Ye use kar le, but aisa nahi h ki bas yahi aisa playlist h jo useful h.. lol.. dekh ke kuch ni hone wala h unless you practice
I am literally watching it like a webseries were I am always curious about what will happen in next episode and it is always hilarious 🔥❤️
exactly 😂💯
basically a suspense thriller😅
Exactly, Whenever I start a new video a suspense is there that what new technique he is going to apply . literally Loved it......!!!
exactly
same!! i concept i was afraid of is so interesting now
Teaching alone in room :- "Ye question sab questions ka BAAP hai"
Mom enters the room :- " Ye questions sab questions ka Parent question hai " 😂😂
😂😂😂😂😂😂😂😂😂
@@TheAdityaVerma bhai sach btao aa to nahi gyi thi mammi kyun laga to sun k esa hi.
@@TheAdityaVerma bhaiyya please put a video even though you don't teach anything. missing you kinda haha
hn bhai
@@TheAdityaVerma How can we count all palindroming subsequence of a string Using this approach ??
i never imagined i would feel confident in dp just by watching 25 videos !
this is the 26th video
@@naiksachin6524 It's 25th only, for programmers counting starts from 0
@@rishabsharma5307 GOod one
When you said that the second string is redundant, I realised that here the second string would be reverse....And LCS again...Thanks for making things such easy for us....
Thanks for watching brother !! You really have a sharp mind, not my credit 😅
same here
I guessed it even
before
I have never been so excited to study dp before. 😁 I am excited to watch every next video and understand concepts which I once thought equivalent to rocket science, and now it's so much fun 🔥
All credits to you legend ❤️
Thanks Prachi 😅✌️
@@TheAdityaVerma you are legend. can you also please upload other remaining topics like kadane's and Fibonacci questions
@@shlokbansal5452 achha just tell me, will this be done without actually reversing the array and, by making j= last element, and check a[i] == a[j].... and hence
@@mayukhchatterjee5998 yeah we can
int longestPalinSubseq(string a) {
//code here
int n=a.length();
vectordp(n+1,vector(n+1,-1));
for(int i=0;i
@@shlokbansal5452 watch striver for rest topics and match it with his pattern.Thanks
Before you tell me the approach to reversing a string, my mind already came up with the idea of reversing the string and applying LCS to achieve the result. You are truly next level 🔥. Thank you so much ❣
Spoiler alert daal deta vro ,XD
@@23cash86 lol😂
true 🤣@@23cash86
Due to your great teaching skills i figured out that we have to reverse on my own. Thanks for this great course on dp.
seriously dude, me too
+1
+1
@@prajwalagarwal8425 me too
26 of 50 (52%) done! Very good expl of logic!
Your 2 years ago comment motivting me now.
@@propubggamer2222 your 1 year ago comment is motivating me now.this shows how great teacher he is,every year someone new comes and learns from this goldmine.
It looks like for the first time i am binge watching a course series....
I listened to problem statement and voila, I had the solution in my mind within 30 seconds. All because of this playlist. Thank you so much!
Very nice and unique explanation, can't imagine it was that easy. I could never understand the table every one start filling for this problem. You made it super easy. Thank you.
ya monika
Your casual approach to solving problems is simply awesome. As I am watching your videos, I think that is the key skill to learn. Dumb down the problem statement and think through the patterns. Great job !!. Please keep it coming.
This exact question was asked in coding round and I explained it just like this, I could say the interviewer was impressed by this approach. Thanks Aditya Verma for making these videos 🙏🙏🙏
Bhai kaunsi company k wo nhi btaya aapne
One of the best playlist I have ever come across in UA-cam. This will really help new graduates and professionals
49 sec in and i have a logic in my mind of comparing the string with its reverse and finding lcs. You're a great logic builder
longest palindromic subsequence---> reverse ur string
longest increasing subsequence---->sort ur string.
do lcs.
for longest increasing subsequence, sort will not work as it will give longest non-decreasing subsequence.
For LIS, we need to both sort and remove duplicates.
@@jayantsharma5209 @jayant bro why it wouldnot work .I am not able to come up with a counyer example . Can u help me .
@@manishmalhotra5883 because in longest increasing subsequence problem the choosen subsequence should be strictly increasing i.e [1, 2, 2, 3] is not an increasing subsequence it is non decreasing subsequence. So by removing duplicates we can make it longest increasing.
How to find longest bitonic sequence in an array with this approach?
Thanks man!! I was struggling with the LIS problem.
I see a lot of comments on this video on how to solve 'Longest Palindromic substring'. The method of LCSS(s, rev(s)) will not work in this case (can be easily shown by few counter-examples). However the question in itself is very easy to solve and requires nothing more than memoizing the recursive solution. We simple pre-compute and store whether s[i...j] is a substring or not in a DP[n][n] table.
Code:
bool isPalindrome(string &s, int i, int j, vector &dp){
if(i>=j) return true;
if(dp[i][j]) return dp[i][j];
if(s[i]!=s[j]) return dp[i][j]=false;
return dp[i][j]= isPalindrome(s, i+1, j-1, dp);
}
string longestPalindrome(string s){
string res="";
vector dp(s.size(), vector(s.size()));
for(int i=0; i
Well it will work, heres how
class Solution {
public int longestPalindromeSubseq(String s) {
if(s == null || s.isEmpty()) return 0;
int n = s.length();
String rev = new StringBuilder(s).reverse().toString();
int[][] dp = new int[n + 1][n + 1];
for(int i = n - 1; i >= 0; i--){
for(int j = n - 1; j >= 0; j--){
if(s.charAt(i) == rev.charAt(j)){
dp[i][j] = 1 + dp[i + 1][j + 1];
}else{
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
return dp[0][0];
}
}
I literally cannot believe I came up with the solution before even watching the video, have always been so scared of DP but now I'm getting comfortable with it. You my friend are doing god's work, Thank youuu.
one word for you sir, You are literally a gem ! , the way you explain can't be matched , I wrote the recursive sol for LPS just after watching the ip and op format. :)
i want to thank you from bottom of my heart ....although i am learning dp for the first time,but after watching one or two videos of this lcs series i am able to solve every question on my own just by looking at the problem statement..these videos are not just videos but blessings for all who are preparing for coding interviews!
the way you broke down how to figure out how to convert this into an LCS was pure genius. That type of thinking is absolutely helpful. The way it clicked for me was incredible
You are gem of dp. You made it so easier for all students to understand.
College seniors recommended his playlist for DP ,i recommend this to my juniors and the cycle goes on. You and your work will be immortal DP king
Bro the way you explain dynamic programming, hats off to you. Never ever saw anyone explaining DP so perfectly. Watching the playlist on a binge mode.
You're simply the GOAT, Aditya, thank you!
Really sad to see low views on such great content 😔
Best of luck brother 💪 this is excellent content 👍
As I was afraid to solve the problems But you made it easy Now I am solving the problems with confident Thanks sir
Thanks for this playlist brother. I was able to figure out the solution very quickly when I thought in the direction of LCS. Thank you
I'm watching this to prepare for my placements and it's really helping me. If I got a decent placement I'd like to give you a treat 😂😂.
bro kya hua? Hope you got a dream package.
Yes I got placed in a good company. Aditya Ji party kab loge ✌️✌️
Your content really helped me prepare for placement tests and interviews.
Thank you ❤️❤️
@Anmol Dogra bhai nhi behen
SAP labs hua✌️
@@anmoljain365 ehhhhh anmol ladki ka naam? omg my whole life has been a lie
@@anmoljain365 congo!!!
Seriously 2 mins in video, maine pause kia and i was able to think of solution myself. kuch to tumne sikha dia hai yar, amazing work!!!
"Oh Fuck" 3:25 XD. Absolutely love this series. "Thanks".
I came up with the right approach in first sight.
Thank you sir 💐💐.
You made me confident in dp 🙏🙏.
You are really a magician, every video is like a suspence which is revealed in the end . Most of time I was clueless and not a single time i lose the focus.
bro this playlist is one of the best playlist I have ever seen in my life on any subject.
One word - MindBlowing Explanation!
03:25
Best channel on youtube, crystal clear explanations and amazing concepts.
my mind is blown. I have never seen such an approach for palindrome sequences. kudos, man.
This is really helpful. Thanks a lot for such an eloquent explanation. After watching this playlist from the beginning, I was able to guess the solution on my own after understanding the problem statement! You're the MVP of Dynamic Programming. Keep up the good work 👍🏼
But this trick doesn't apply to Longest Palindrome SubString. for IP "aacabdkacaa"
If I reverse the given string to form a second string and if I apply the LCSubstring logic it gives length 4 (aaca) which is wrong.
Ur LCS is incorrect it should be aacakacaa
@@adityaramakrishnan969 yes.
@@adityaramakrishnan969 achha just tell me, will this be done without actually reversing the array and, by making j= last element, and check a[i] == a[j].... and hence
Thanks bhai apne itne sikha dia pichle videos m ki ab main khud s soch sakta ki ap is ques m kya karoge.
Dil s Dhanyabad 🤗
Thank you! This made my day. Already on the 26th and i started today. Can you put 27 video again?
Bhaiya, You've taught me what no one else could....
You taught me how to think!!
I could solve dp problems on my own :))))))))
You don't know how thankful I am right now!!
you are our savior bhai. Sharing this level of content for free is something really great from you.
why g was not taken. in the reverse of string g is also present
1:36 Style hai bhai ka Style!!!!!
Your teaching skills and logical reasoning is on next level sir
Your explanations are amazing.Can you please make a series on trees and strings as well.Would be very helpful.
Bhai vdo no 27 is no longer available ....plz update the list
Great video series:)
Please make video on "Longest Palindromic Substring" as well
Like Longest Common Subsequence is to Longest Palindromic Subsequence, It is Longest Common Substring to Longest Palindromic Substring
Sorry, above approach will fail for "abcdba"
@@prateekchs exactly! so whats the soln?
Yes but why it is not working like lcsequence work for lpsequence
Lcsubstring should also work for lpsubstring
u made me this ... before seeing the video i knew the answer, i cant thank u even. I dont know either u r great or not but the thing is ur conept made me this. definitely i would suggest your videos to everyone.
I never ever watch this kind of explanation its superb bro but please upload further videos like
Sorting and so on, please upload 🙏
Thanks, Will upload soon. Please share to help this channel grow.
@@TheAdityaVerma sure and I have been waiting for further videos
Thanks
Your observations are just lit,,never seen someone generalising every problem and connecting to some other problem like you are doing,,Hattssss offffff bro!!!!
This is surely the best content online for dynamic programming. Really thankful to you bhaiya.
Man its day-4 for me watching it from video-1 and this is like a blessing for we dp learners. And we are so thankful that u kept these for free, somebody else might have kept high prices for these. For dp from which i was so scared, I m excited nowadays.
The way he explains is so good that it's messing the way I think...😲💯
I am going to plan an idea in your head without you knowing it.
I hope you have watched inception :P
@@TheAdityaVerma please put the 27th video
I solved it without seeing your video you teach so well man hats off to you.
The logic of this question is simply beautiful!
Your videos have developed my thinking in DP...I was able to guess that we have to reverse the string way before you told...Thanks man...best playlist on DP
Bro.. what microphone, camera and stick u use to keep in such position can you say? It's nice and interesting!! 😇
Brother tbh I dont remember now what I ordered !!
@@TheAdityaVerma please put the 27th video again
I think we cannot solve the longest palindromic substring problem using LCS pattern.
example: str: abcdba, it's reverse it 'abdcba` . if we find longest common substring then it will be 'ab' or 'ba' and both are not palindromes.
I came this channel to watch one video but one by one i watched whole playlist
Amazing explanation
very helpful videos brother
I can't contain myself to NOT like your videos.....
Sir you might not even know but you are doing WONDERS in student's life...
College doesn't even provide 10% of what you do in minutes !
A big THANKYOU @Aditya Verma Sir !
@Aditya
Tu toh deo manush hai re baba
Thank you so much Aditya sir
Apne Bhai jaisa koi hardich nahi
can we solve longest-palindromic-substring using lcs?
Even striver bhaiya recommended this pure gold :)
Awesome bro!! I am following you from 1st video and you make dynamic programming so easy for us. Thanks a lot....
3:30
That emotion😂🔥
can you also do explanation on: Longest Palindromic Substring plz
That's actually just parallel use of longest common substring instead of Longest common subsequence.
Video on "PRINTING LONGEST PALINDROMIC SUBSTRING" plzzzzzzzzzzz...
Thank youuuu sooo much sirrr!!😍😍😍. This playlist is a gem and so are you !😍
27th is missing in this playlist, it says it's private. Please take a look
@Aditya Verma Can I use the same technique to solve for Longest Palindromic substring?
thanks brother
u are gem
watched your 25 videos and all are just amazing !!!!
Bro... hats off to you seriously.... No one can explain better than you.
the main thing i have learned from you is analysing the question and i have did that thanks a lot brother
Thank you so much Aditya sir , this is a lifesaver playlist for placement students who are afraid of topics like DP ....after this i am able to solve questions like a pro !!
Bhaiyaa mazaa a gayaa!!!! DP is no more a hard topic. I have gone through your video thoroughly with a speed of 0.75 including ohh f**k @3:25 ...............Graph ka bhi banaa do bhaiyaa
Bhai Kya Mast Pdhaata hain yaar tu. Literally Neend aarhi thi DP ki yeh video dekhni shuru ki Sab Gayab. Maza Aagya Bro.
Aur Yeh 4 Dislikes waale Sudhar Jaoo yaar Bhaiya itni mehnat krrhe so Like nhi krna plz dislike to mat kro
Waiting for the Next Graph Series :)
I figured out the algorithm just after 20 sec in this video, after watching all your previous videos. THANKS. ✅✅👌👌
this playlist is similar to a web series , If you miss any episode then you wont be able to understand the next lecture. love you sir. deep respect for you.
par meri ek shikayat hain , ab aap videos kyu nahi banate aap ek aditya verma dsa parent of all courses nikaliye chahe paid pls , aaap se hee padhna chahte hain.
You are truly a great teacher, after watching all these videos, I knew how to solve this question just by reading the problem statement.
All credits to you legend ❤
Submitted this question before watching the whole video...!!!
power of aditya verma's dp playlist.
why 27 th video is not showing?
I first solved this question by watching the explanation of some another channel, I'm simply amazed to see this solution. It is far more logical and easy.
I tried to print the longest palindromic sequence after solving this, but it is giving some uncertain results..help out..!! maybe because while backtracking if t[i-1][j] == t[i][j-1]....is there anything i am missing.?
The best DP series
How to say thanks to you I don't know. your videos are so interesting that makes me interest in programming . love you bro
Damn!!! what a logic man! hats off literally!
I am following this playlist for palindrome I saw various approaches on various sites but this is wonderful
Bro if UA-cam has it own museum they should save this playlist for our future generations...bhaisahab keher ...
Keep uploading sir
It helps us a lot
Thanks for making this type of contents
i was able to identify the approach fairly quickly. I myself am surprised. Great resource. It's the way you are repeating and stressing on the approach and how to think is what is making this playlist such great thing. You should maybe dub this in English too for wider reach. Would also be helpful to add the problem links of leetcode or other platforms, where we can practice the problem in description if possible. I prefer leetcode, you know why :). Its just convenience.
You should make your own merch "Acha... Theek Hai"
Viewers - Who's your DADDY?
DP - Knapsack and LCS!
thanks sir now i am able to create dp code by my own..... even after solving a problem i do watch video for satisfaction... 🤩
I could think of solution before starting the video. your explanation is great!!
Brother, this playlist is gem !!
Great content!! Please keep making videos like these!
Soln for "Longest Common Palindromic Substring" in java in leetcode
Brute force method:
class Solution
{
public String longestPalindrome(String s)
{
if(s.length()