DP 29. Minimum Insertions to Make String Palindrome
Вставка
- Опубліковано 22 чер 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 👍🏻
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
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 ...
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
TOTALLY UNDERSTOOD... !!!
That just blew up my mind...
Thank you striver for the video... :)
i did this by own !!! i am loving it that i came up to the solution by own . Thank You Striver !!
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.
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!!
hats off to you !!! Proved that , every topic is easy if you got the right teachings..
Solved this without even watching. Thanks bro
me too
UNDERSTOOD.......Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
Waoooh... Previous lecture concept move this LC hard level question to medium level
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!! 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?
understood, thank you so much.
Thanks a lot bro..... I really appreciate you!
Understood! I really really appreciate for your explanation!!
got the logic just after your first exmaple. Thank you Raj bhaiya
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. Thankyou sir
hats off to you
Terrific explanation. Thank you so much !!!
8:06 promotion at its best XD. Understood as always Striver!
Bhaiyaa we are so so grateful for your content and effort🙏❤
Understood, sir. Thank you very much.
Understood sir!
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
Understood. Amazing explanation!
understood sir, u are amazing , love the way u teach.
understood!!.
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
Understood ❤
Thank You
Understood!!!!!
Understood!!!Thank you
please do word break & word break ii. thanks
BESTTT TEACHERRR EVERRR!!!!!!!!!!!!!!!!1
Understood!
your videos are awesome. Please suggest system design related training
This is a Hard category question on leetcode but u made it a piece of cake lmao ❤
Awesome!! 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
Understood !!
got the idea @ 5:19 we can do length()-LPS thank you striver for such amazing videos
Understood, thanks a ton
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 Sir thank you very much
Just want to say... You are awesome striver😇😇
Understood Thanks Striver ❤
understood :)❤
Best❤
Striver thankyou
first time in dp i did this question without watched your video
thanks
ye badhiya tha guru...ji...
We are glad to have u brother
Understood
Understood !!!!!
US, mindblowing explanation
understood
Understood. You made dp easy.
All Character (at opposite position) which are not part of longest palindromic subsequence
bro made leetcode hard look like a lollypop thanks striver loving this dp series
LCS is just Like Striver....It helps us to solve most of the problems ........Sorry for the PJ #UNDERSTOOD
Understood🌻
understood bhai , thanks !
understooodd!!!!
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 29/57 completed!
understood 👍
understood bhaiya❤❤
Understood🔥🔥
how can we print the modified string which will be palindrome string after minimum no operations
😅 Understood 😊
Done and dusted in DP revision
Nov'14, 2023 05:54 pm
How to print the converted string? I mean after insertions, The final palindromic string
Seems to be very tough!
Understood 🎉
Understood !!!🥰🥰🥰
Understood 👍
UNDERSTOOD ...
Understood.
understood!!
Bhaiya muje string ke question mai bilkul confident nhi hai mai wo kese strong kru aapne?
Understood❤
Understood 🥰
Thanks
Enlightenment
Great!!
this question was rated hard in leetcode after seeing ur explanation i was like why is it rated hard?
Understood!!!
Understood kaka!
understood❤❤❤
*As we are not passing the string by reference '&' then also the code is running fine, can anyone explain this*
Apparently this playlist is sponsored by Coding Ninjas, Best marketing move.
US, half playlist completed😄
understoood bhaiya
Understood sir🙇♂🙏❤
understood 😄😄
Great