DP 29. Minimum Insertions to Make String Palindrome
Vložit
- čas přidán 23. 07. 2024
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3H2ZtGP
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 minimum insertions to make a string palindrome, before watching this please make sure to watch the DP 28 video.
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
The ans for minimum no. of deletions to make a string palindrome will also be same because if we just remove the characters which are not a part of the lps(longest palindromic subsequence) we'll get the ans...which is same as n-len(lps)
this is making more sense to me.......
Great 👍🏻
Yes, you're right. Thanks
Previously, I heard that DP is some sort of topic, people use to leave, but now after watching each and every video of Striver, I must say you just made it the easiest.
Write the recursion -> change it to memoization -> change it to tabulation.
And the relation you develop between questions, is just incredible. Keep growing.
dp is a marathon not that tuff , if teacher is good its a cakewalk
TOTALLY UNDERSTOOD... !!!
That just blew up my mind...
Thank you striver for the video... :)
Hi Striver, I have been following your videos for the past three months and dp series since last week. I really had to admit how graceful you are in teaching, I thank you a lot for your contribution and today I solved myself this question without looking into the solution and now I am going to watch it to make a note of your points if I had missed anything. And since I started your dp series, I have handwritten all the things that you had said and I am also finding it very useful for revision. Thanks again
Can you send me those notes
i did this by own !!! i am loving it that i came up to the solution by own . Thank You Striver !!
52% done .... striver bro u build my logic ... now i can solve any pattern of dp taught till now .... and also i solved all the problems by myself when u just write sudo code for new topic .... thanks striver bro ...
man GOD level stuff Striverrr, it was a leetcode HARD problem, but the logic you told makes it look a EASY level problem!!!! Thanks a lotttt!!
I initially tried with my own and with way you teach I was able to solve it by my own.
Thanks understood one more lecture.
Solved this without even watching. Thanks bro
me too
hats off to you !!! Proved that , every topic is easy if you got the right teachings..
Understood! A small clarification - at 8:35 , when you kept the palindromic section in tact, shouldn't you have taken "cod" instead of "codi" while switching? That along with "sajn" would give the minimum insertions to be 3+4 = 7 right?
ya it was by mistake he did
did this que by myself , thank you striver
Understood....the way u explain DP, seems like DP is piece of cake!!
"Logic formed just by seeing example test cases" came to video to insure that i am thinking right THANKU Striver
UNDERSTOOD.......Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Amazing , thanks Striver
Waoooh... Previous lecture concept move this LC hard level question to medium level
got the logic just after your first exmaple. Thank you Raj bhaiya
Understood!! LCS pattern can help us solve so many problems!! Thanks Striver
LCS?? What's LCS, He was saying LPS or LCS!??
@@Mojemoye LONGEST COMMON SUBSEQUENCE
@@Mojemoye lps will also be done by lcs
One question; Is LCS pattern enough for solving any dp on string problem?
man hatsoff to you striver
Intuition just clicked in by just seeing the topic of video,
and converted it into code under just 5 mins and easily did a leetcode hard problem
so thanks again striver for such an amazing content
8:06 promotion at its best XD. Understood as always Striver!
Understood! I really really appreciate for your explanation!!
Terrific explanation. Thank you so much !!!
Bhaiyaa we are so so grateful for your content and effort🙏❤
Thanks a lot bro..... I really appreciate you!
Understood, sir. Thank you very much.
Bhaiya i understood the concepts upto dp on subsequences very well also did the questions without watching or seeing the solutions but this dp on string topic , i understand the solution properly but can't do problem by my own . Anyway ... understoo the solution. Thanks ❤
understood, thank you so much.
hats off to you
Understood. Amazing explanation!
Understood. Thankyou sir
understood striver !!!
This is a Hard category question on leetcode but u made it a piece of cake lmao ❤
understood sir, u are amazing , love the way u teach.
Minimum Insertions To make palindrome = (length of string - * length of longest palindromic Subsequence *) [DP 29],
and Length of Longest palindromic Subsequence = (* longest common Subsequence * between String and its Reverse ) [DP 28]
And longest common Subsequence, we know it already !! [DP 25]
What a link !
matlab questions naye ate jaa rhe h bss , baki jitna sikha h unhi me se uska solution mil rha h, thoda observation acha ho toh 😀
man gye bhai ! ❤
Itni ache se design ki h playlist ki aap gadhe se Gadhe ko bhi sikha skhtein ho, bs uski sikhne ki ichha ho
Understood sir!
BESTTT TEACHERRR EVERRR!!!!!!!!!!!!!!!!1
Understood ❤
got the idea @ 5:19 we can do length()-LPS thank you striver for such amazing videos
great video
understood!!.
Understood!
Thank You
Understood!!!!!
understood!
thank you
demn i just tried the question first without starting video, just changed return dp[n][n] to n-dp[n][n], and lol it worked, and on leetcode it was a hard ques, I didn't believe, so I saw ur video, and yea it was indeed easy, after doing the LPS ques.
Understood Thanks Striver ❤
We are glad to have u brother
Understood!!!Thank you
Just want to say... You are awesome striver😇😇
Understood !!
Awesome!! Understood!!
please do word break & word break ii. thanks
Understood Sir thank you very much
Striver thankyou
first time in dp i did this question without watched your video
thanks
Best❤
bro made leetcode hard look like a lollypop thanks striver loving this dp series
understood :)❤
Understood, thanks a ton
how can we print the modified string which will be palindrome string after minimum no operations
Understood. You made dp easy.
your videos are awesome. Please suggest system design related training
All Character (at opposite position) which are not part of longest palindromic subsequence
US, mindblowing explanation
Understood !!!!!
*As we are not passing the string by reference '&' then also the code is running fine, can anyone explain this*
Understood
ye badhiya tha guru...ji...
understood.
understood
How to print the converted string? I mean after insertions, The final palindromic string
Seems to be very tough!
Understood🔥🔥
understood bhai , thanks !
understooodd!!!!
Understood🌻
Apparently this playlist is sponsored by Coding Ninjas, Best marketing move.
understood 29/57 completed!
Done and dusted in DP revision
Nov'14, 2023 05:54 pm
Bhaiya muje string ke question mai bilkul confident nhi hai mai wo kese strong kru aapne?
this question was rated hard in leetcode after seeing ur explanation i was like why is it rated hard?
Understood Bhai. Have a request. Is it possible to explain the logic and code for the "look and say" or "count and say" problem bro? thanks in advance. it would really help if you could.
understood 👍
understood bhaiya❤❤
Understood 🎉
😅 Understood 😊
UNDERSTOOD ...
i did this question in another way and that is accepted with 100 % score.
Kindly take a look....
Memoized solution -
int f(int l, int r, string &str, vector &dp)
{
if (l >= r)
return 0;
if (dp[l][r] != -1)
return dp[l][r];
if (str[l] == str[r])
return dp[l][r] = f(l + 1, r - 1, str, dp);
else
return dp[l][r] = 1 + min(f(l + 1, r, str, dp), f(l, r - 1, str, dp));
}
int minInsertion(string &str)
{
int n = str.size();
int a = 0, b = str.size() - 1;
vector dp(n, vector(n, -1));
return f(a, b, str, dp);
}
Tabulation -
int minInsertion(string &str)
{
int n = str.size();
int a = 0, b = str.size() - 1;
vector dp(n, vector(n, 0));
for (int l = n - 2; l >= 0; l--)
{
for (int r = l + 1; r < n; r++)
{
if (str[l] == str[r])
dp[l][r] = dp[l + 1][r - 1];
else
dp[l][r] = 1 + min(dp[l + 1][r], dp[l][r - 1]);
}
}
return dp[a][b];
}
Thanks Striver for this complete DP playlist.
what is your dp state?? means what dp[i][j] represent
stack space for memoized solution is O(2N) right?
Thanks
Understood.
Understood !!!🥰🥰🥰
Understood 👍
Understood 🥰
Understood❤
US, half playlist completed😄
Understood kaka!
Great!!
understood!!
did anyone try this question on leetcode the string in testcase 2 can be made a palindrome in just 1 move by adding a t at the beginning i.e tletelt , all the characters in this string get cancelled out
Understood 🙂🙂💚💚
This is rated Leetcode Hard but i thought it was easier than other DP Strings