Palindrome Partitioning with Minimum Cuts Dynamic Programming | Minimum Palindromic Cuts
Вставка
- Опубліковано 12 вер 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. Here you will learn about Minimum Palindromic Cut in Dynamic Programming. In this question:
1. You are given a string.
2. You have to find the minimum number of cuts required to convert the given string into palindromic partitions.
3. Partitioning of the string is a palindromic partitioning if every substring of the partition is a palindrome.
To attempt and submit this question, click here: www.pepcoding....
For a better experience and more exercises, VISIT: www.pepcoding....
#dynamicprogramming #palindrome #leetcode
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
Thank you for the video, it feels like aap actually interested ho ki viewer concepts ko samjhe. That is a very rare quality with such videos.
I am glad. Keep learning. Keep supporting. Your kind words are the kind of motivation that truly help me in making more and more content. Especially, these days, not everybody is generous with motivating anybody either. It means a lot😊
After facing disappointment from the videos of other channels, this video proved to be a saviour for me, or otherwise I wouldn't have got the solution to this problem. Thanks a lot!!
It's a treat to watch your content Sumeet bhaiya. specially DP. The way you don't just tell the solution but also hidden why's and sought of entire research each and every question is really helpful for me and sure for other people as well. I am sure this content will really be helpful in creating epic developers and founders in India, I have been your student in classroom and always see same dedication and intent in youtube videos, as you have while teaching in classroom, perhaps even more. You really inspire me to put in same dedication into my work as you do. Thanks Bhaiya :)
Thanks a ton ! For more content like this please visit nados.pepcoding.com
You just make every problem look so simple with your detailed explanation. Great efforts!!
Earlier I was like it is a lengthy video but after I started don't know when time passed. Thanky you Sumit sir for such high quality and engaging content.
sir on youtube only your's video give clear understanding for dsa questions mostly the backtracking and dynamic programming questions
Thank you Nitesh :) To watch more content like this with a better user experience visit nados.pepcoding.com
THANK YOU SO MUCH FOR THIS, was literally on the verge of going crazy because the n³ solution kept throwing TLE, until I found this vid, great explanation, thank you.
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
Sir hats off hai aapko. itna patience se padhana mjaak nahi hai. No words to explain right now . Thank you sir
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
@@Pepcoding done sir
It was such a breeze to understand each and every concept in this problem! Thank you bro
Thank you so much 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 )
Using prefix strategy:
int n = s.length();
for(int i = n - 1; i >= 0; i--) { // As we want the right side of strg[] to be filled initially, start traversing from behind.
if(!dp[i][n - 1]) {
int min = Integer.MAX_VALUE;
for(int j = i; j < n - 1; j++) {
if(dp[i][j]) {
min = Math.min(min, strg[j + 1]);
}
}
strg[i] = min + 1;
}
}
return strg[0];
Thank you so much for the video sir. Great effort! Extremely helpful!
Dil se thank you Sumeet Bhai
can you please tell , in which video of yours ,gap strategy is explained?.....There is no video named as gap strategy .
@Pepcoding where can I find gap strategy
This code is not working for the string "aaabba". Could you please help?
Very nice explanation sir....really good video...I truly appreciate your work
Bro , literally your videos are very helpful, thx a lot for these wonderful videos
Thank Bhai. Keep learning, Keep growing and keep loving Pepcoding!😊
Sir one more thing
Like in the end if there a prefix palindrome it will fail ex:- "aab"
solution to that is:-
for(int k=0;k
maza bhi aa gya aur samaj bhi ek number sir🔥🔥
Very nice explanation.. Pehle 2 videos dekhi thi.. Par concept samaj Nahi aaya... After this I got it!! Thank you
bhaiya thanks for great explanation,
only small question is on website, In level 2, under DP, sequence after Matrix Multiplication is not matching as per your videos,
as next 4-5 videos are ordered in reverse order, please check as per dependency of videos is matching to order.
sir how can we generalise the questions , will this soltuion of variation of mcm could be used anywhere too?
Dhanyawad
Thank you so much bhaiya
probably you and abdul bari sir are best on youttube for algos
Your explanation is really good to understand. Thank you for making these videos.
Thank you so much 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 )
Sir, you are such a fine teacher.
Yes, every explanation simply touches your heart. That's pure teaching from Sumeet sir.
BTW Himanshu, I am also at this level only in level2. Are you doing DSA regularly?
Not currently Ankit. I have passed out from clg.
@@hymnish_you Well pass out or not is not an issue. Anyways happy learning!!
Thanks for creating such as awesome content sir.
Glad it was helpful!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
one of the best explanations!!! Thank you
Very smooth and nice explanation sir !!
Nobody explained it better than you..sir
thank you so much. ajkal to bache motivate bhi nahi karte. jo karte hain unke hum tahe dil se dhukargujaar hain. aapki support se he content bnane mei bhot madad milti hai
Fantastic... !
Great explanation !
Thank you for explaining in such beautiful way.
Glad it was helpful!
For better experience and well organised content sign up on nados.io
And for being updated follow us on Instagram instagram.com/pepcoding/
Thanks for creating such as awesome content.
Superb Explanation
Thank You so much sir for your videos
I am having doubt what kind of questions that we need to solve for coding round?
All these questions are for coding round or interview round?
Thanks a lot. I was stuck from last 2 days.
great content sir.No one teach like you.
Why does the approach of taking only palindrome prefix/palindrome suffix reduce time complexity?
For solving all your doubts, post your doubts on community tab of NADOS. Visit on nados.io
Which video explains the basics of gap strategy from beginning
Sir, can you please share the link to the video where you have explained the gap strategy.
bhai mili?
@@theuntoldtree count palindromic substring wali video hai
best explanation possible!!
really very helpfull......thank you 4 ur hardwork
like your teaching methodology
gap strategy?? which vedio to refer
Really great explanation. Thanks for providing such content.
Thank you so much 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 )
sir mere ko n^2 vala samaj nai aaya. aap ek side se palindrome kyo le ke chal rhe hai?
Loved the video, great explanation
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
great explanation sir, learned something new!(gap method)
best video on youtube right now!
2nd approach was lit 🔥🌪
where is the gap strategy tutorial link?
Sir test cases standard hote h na coz may be practicing on weak testcases causes issues in the real interviews
please include all the variations of test cases in the problem.
BTW Sir u are doing great work, honoured to learn.
is this video in english somewhere else?
Can anyone please provide the link to Gap Strategy video of Sumit Sir?
Thank you sir for this awesome details teaching
So nice of you 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 )
Gap strategy wali videos kain si hai ? Please bta do koi ! Please
Sir yah Gap strategy konse Video mai explain ke hai ?
You will find the gap stratergy in this question -www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/dynamic-programming/count-of-distinct-palindromic-subsequences-official/ojquestion
@@Pepcoding its not there sir
i one of the best channels even
thank you!
Sir interview me bas approach batani hoti hai ya yeh bhi explain krna hota hai vo approach humne kaise sochi? Like how did we come to that approach?
super awesome explanation
please explain the code from line 9 to line 23 , the loop ,
can you do this problem in recursion without going directly into DP sir?
Code is wrong. below is the correct version. A little mistake . Second loop while go end till 0th index.
int cuts[n];
cuts[0]=0;
for(int i=1;i=0;j--){
if(j==0 && isPalindrome[j][i]==1){
val=0;
}
else if(isPalindrome[j][i]==1){
val = min(val,1+cuts[j-1]);
}
}
cuts[i]=val;
}
Sir is there any recursive approach for the same. jumping directly on the bottom-up solution seems hard.
Ji. I will soon do memoization
Pretty good video .
In the initial part when we are discussing the basic premise for the question before cutting we can make a check for the case when the whole string is palindrome otherwise that case if left ?
yes we need a case there beacause by first way we already are adding a +1 of making a cut , if there is a string which has plaindromes in it but itself is a plaindrome too ,we will get wrong answer
Just awesome
Can anyone send the link of vdo where gap strategy is explained throughly??
Thanks a lot sir.
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
Thank you Sir
For better experience and well organised content sign up on nados.io
And for being updated follow us on Instagram instagram.com/pepcoding/
Thanks. It is very tough solution.
Glad you learned. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding Done
sir sawal thoda mushkil laga par ho gaya, thank u sir, east or west sumeet sir is the best
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
this code is not working
OP 🔥🔥
sir , in which video u have taught the gap statergy ?
For such queries sign up on nados.io and post your queries on community section of NADOS, our alumni and mentors will help you.
mazaa aagayi sirji
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Ye gap strategy kya hai prerequisites me jo apne bola? Wo palindrome wala mtrix samaj me nai aya.
Haan jii
At 19:00 did you say gap search? I'm hearing it for the 1st time.
Can anyone say what exactly it is? Thank you in advance
see count palindromic substring where gap method is discussed
1:04 " to dekhiye hum kese karenge isko " , sir please insert that " bhai ye kese kar raha h " meme here 😂😂
ok ji
Why don't you use recursion + memoziation here ?
because recursion + memorization code is giving TLE at all platform interviewbit,gfg,leetcode.
28/79 Done
Keep going. And for better experience and well organised content sign up on nados.io and keep learning.
Sir BNY mellon ka hacker earth par trst hai oct mid mein kuch tips mil sakte hai prepration ke liye
Foundation kar chuka hoon
Aur l2 aapke saath kar raha hoon
beta geeksforgeeks se BNY mellon ke interview experiences dekho.
Sir where to watch gap strategy?
For better experience and well organised content sign up on nados.io and start learning.
O(n^3) solution shows TLE on LeetCode and GFG both.
Sir ye topic book me to hai hi nahi.
Shivam Agarwal bhaiya aap pls bata sakte ho ki aap konsi book ki baat kr rhe ho, please bhaiya book ka naam ya kuchh source bhej sakte ho kya, thanx🙏
DP level 2 me 3 videos private ho chuki hain sir.
Please look into it.
beta private walio mei kuch galti hogi. kuch private nahi rakhna, jo content hoga sara public hoga
29:52
Sir yeh determine nahi kar paa raha hu ki dp array kab use karni h
beta, 150 questions solve karne ke baad dikaat nahi hogi
@@Pepcoding thnk u sir
for "efe" im getting wrong ans acc to this approach on leetcode...expected ans is 0 but this code is giving 2.
same bro
Sir you haven't explained gap strategy method thoroughly in any of your vdo... despite I have been watching your video in series.
me bhi kab se yahi dundh raha hu ki konsi video me sir ne sikhaya hai gap strategy pr mila hi nhi toh kaha se sikha bro aapne?
@@amaan8617 Count palindromic substrings
Sir ji Burst balloon
ok beta. ek do din mei aa jaega. maine likha hua hai.
SIR PLEASE YE BTA DIJIYE KI GRAPH KE QUESTION KAB SE START HOGA PLEASE SIR
Abhi DP ke jis din 150 ho jaenge. Abhi abhi 62nd bnaya hai.
Jo h vo smbhal ni rha ye kb vo kb
Sir g speed increase kar lo please request, abhi shayad DP aadhi bhi nhi hui hai🙂
han beta. poori koshish hai.
62 out of 150 hue hain
7 dislikes are by those jinke string me distinct characters h 😅