Count Distinct Palindromic Subsequences Dynamic Programming | Leetcode Hard Solution
Вставка
- Опубліковано 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. In this video, we discuss the Count Distinct Palindromic Subsequences problem using dynamic programming. In this problem,
1. You are given a string.
2. You have to print the count of distinct and non-empty palindromic subsequences in the given string.
3. Two sequences s1 and s2 are distinct if here is some i, for which ith character in s1 and s2 are different.
Note - String contains only lowercase letters.
- The answer will be in the integer range only.
To submit this question, click here: www.pepcoding....
For a better experience and more exercises, VISIT: www.pepcoding....
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
Amazing video!!!! Thank you so much for such a detailed explanation!!!
Best Explanation.
Literally great detailed Insightful video of deriving the formula , Loved it♥
GAWD effort.... Respect
Tysm.
Taking out 100 minutes to on a single question to develop insight, requires extreme dedication. Thank you so much for that
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 I have given the review sir cuz video is superb understood the insight watched whole video
Was better than Watching a Movie.
I am grateful you took out time to watch it
Just amazing
I hit like as soon as his tshirt color changed at 38:00 , he dedicated two days to explain this problem in the best and clear way possible! Hats off to you sir!
Learnt Concept + Allegiance + Dedication.
Thanks to the best DS Algo teacher.
Thankyou beta!
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
@@Pepcoding 404 error, Sir
@Pepcoding team. What great materials you have published . @Sumeet hats off to your dedication and superhuman patience. 1hr 40 mins to explain and clarify a single question that is out of this world. No channel can come close to yours with the the level of details and reasoning you provide behind the solutions . I can't thank you enough.
Not a single second of such a long video was boring! Thanks a lot❤
Thanks a lot @PrepCoding for this phenomanal material, This is something will change the attitude with which we solve our problem. Wonderful postmartum of the probelm.
Sir ,we want more solutions and concepts for difficult problems, you are best
Took me around 2hrs+ to grasp everything, thank you so much for the video Sir
Glad it helped!
This is one of the longest video I have ever seen on pepcoding channel, but I must tell that this is the best explanation video for the problem I walk through most of the videos on UA-cam. I have seen this video twice, though its long but its very important to learn the maths behind the problems rather than just remembering it without understanding.
Thank You #Sumeet_Malik for providing such a wonderful explanation video. #We_Need_More_Videos_Like_This
watched it till end. What an effort you make!!!!!!!!!!!!!!!!! really appreciated. Just dont stop ever.
mza aya na? koi maths ka shokeen dekhega to usko bhot feel aaegi, sirf formula btana asaan tha, full analysis mushkil. isme bhi last ke 2 cases poora mathematically rigorous analysis nahi kia. wo aur hota to aur mza ata.
@@Pepcoding haan but jitna bhi analysis kiya usme bada mazza aaya. Nayi chiz sikhne ko mili. Isme toh distinct palindromic subsequences batane the. Ye video dekhne ke baad mujhe ek sawal mila jisme palindromic subsequences btane the irrespective of ki vo distinct h yaa nhi. Iss concept se ye sawal bhi ban gaya. Tysm.
A big big thanks and shout out to you sir..You made it easy to understand DP and just because of your content i'm able to crack HCL and TCS Internviews for FTE
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/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Sure sir, I will.
There are people who just want to know the technique and code and thats the best part of this video. It caters to all the audiences who wants just the answer and the deeper insight. Love it.
ufff, thats some next level dedication sir, completed it today. tysm sir :)
All the best
Every second of the video was worth watching 🔥
is video ko to koi jhel leta hai to mai grateful feel karta hun
best explanation , no one will explain so well free of cost for so much time...thanq so much!!!!!!!!!!
When I saw video is of 100 minutes, I knew , dekhna Hi padega . Thank you for your efforts !
Amazing explanation!
Watched it along with my own attempt in around 3 hours
Now the concept is crystal clear
Great to hear!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Watched the full video. Thanks for the insight
Glad it was helpful!
Interesting video with the best explanation as always. I watched the full video !! Thank you, 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 my efforts, I request a review
g.page/Pepcoding/review?rc
Ek hai curriculum ki discrete mathematics 😂jo mujhe lagta tha ki kyun hi padhate hain kyunki koi use to dikhta nhi tha coding ques mein,jabse advanced dp start ki hai sumeet sir me bhar bhar ke set theory ke proofs samjha diye. Hats off to you sir, legendary content🙏
If you like the content could you post something on LinkedIn about us? This will help us in reaching out to more people and help a lot of other students as well
Something like this
Sumeet Malik from Pepcoding is making all his content freely available to the community
You can check it out here - www.pepcoding.com/resources
/
Also, this is the youtube channel - ua-cam.com/users/Pepcodingplaylists?view_as=subscriber
everybody gangsta in finding count of all palindromic subsequences until the interviewer mentions "distinct"
Everybody is a gangsta until you have to see a video of 1 hour 40 minutes for one question
@@Pepcoding lmao
Other coding institutes dont have such reasoning in their dynamic programming course content, they just tell how and what, not why.
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
35/79 Done
there are many youtube coding channel which i know but only on your channel i get this question as its difficult to explain,all other channels just covered its med variation that is no. of subsequence in string but pick this up great sir,love the way to teach🧡🧡🧡
you deserve a lot more recognition . (#rising star)
watched this video till end.... and now i can explain with the same confidence as you did.
One of the best explanation. Thanks a lot sir.
C++ Solution for LeetCode
class Solution {
public:
int countPalindromicSubsequences(string s) {
int n = s.length();
unordered_map m;
int prev[n];
int next[n];
int modulo = 1000000007;
for(int i = 0; i < n; ++i) {
if(m.find(s[i]) != m.end()) {
prev[i] = m[s[i]];
}
else {
prev[i] = -1;
}
m[s[i]] = i;
}
m.clear();
for(int i = n - 1; i >= 0; --i) {
if(m.find(s[i]) != m.end()) {
next[i] = m[s[i]];
}
else {
next[i] = -1;
}
m[s[i]] = i;
}
vector dp(n, vector(n));
for(int g = 0; g < n; ++g) {
for(int i = 0, j = g; j < n; ++i, ++j) {
if(g == 0) {
dp[i][j] = 1;
}
else if(g == 1) {
dp[i][j] = 2;
}
else {
if(s[i] != s[j]) {
dp[i][j] = (dp[i][j - 1]%modulo + dp[i + 1][j]%modulo - dp[i + 1][j - 1]%modulo)%modulo;
}
else {
int n = next[i];
int p = prev[j];
if(n == p) {
dp[i][j] = (2*dp[i + 1][j - 1] + 1)%modulo;
}
else if(n < p) {
dp[i][j] =((2*dp[i + 1][j - 1])%modulo - (dp[n + 1][p - 1])%modulo)%modulo;
}
else {
dp[i][j] = (2*dp[i + 1][j - 1] + 2)%modulo;
}
}
}
if(dp[i][j] < 0)
dp[i][j] += modulo;
}
}
return dp[0][n - 1];
}
};
Aapke mehnat ko salam🙏
You are legend sir! God bless you!
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 )
Are you from DAIICT Aditya ?
@@JT-pq1ey Nope, Jaypee Nodia
amazing explanation sir ... really hats off sir 💖
Thanks a ton!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
is this question part of some playlist?
only 338 out of 367 test cases passig on leetcode :(
see my latest comment on this video
Hi Sumit. Thanks for your videos . Its because of your videos i got offer from SAP. God bless you
I'm glad to know that and many congratulations to you. I wish for lots of more succes in your life.😊
Can you DM me on LinkedIn?
❤️❤️Superb explanation 👍😀..
Glad you liked it!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Dil khush kar diya aisa kisine nahi samjhaya hai 😌😭🤧🤧🤧
Thank a lot sir .
sir nados ki site pe ek bhi video ni chlri kl se try kr ra hun
Awesome teacher...
God this was bloody awesome. Thank you so much.
Iss shehar Mei swag hai mera bhai. Hapy new year to you. Analysis dekh rhe ho? Deep hai na?
@@Pepcoding Happy New year to you too.
@@Pepcoding Absolutely I have never see this depth of analysis anywhere.
sir can you tell us which maths topics are must for us to do well in these questions..
if possible can you please recommend any good resources on that.
GOD TEACHER OR WHAT ❤️🔥
Sir ,badi video pe b views ki kami nahi this proves that students are dedicated like you as well,same views ha
Ji..
Keep watching and keep learning😊
Sir in this let's say tha string is abaaca then the next and prev will be 2 and 3 for I=0 and j=5 , so there is no middle part for next and prev but in your code it will ask for dp[n+1][p-1] which will turn out to be dp[3][2] which is invalid so I think you should add a case when p==n+1 , your code will run even without this case because dp[3][2] will be zero (default value is 0 in java ig) but it is good to acknowledge this because in c++ there can be garbage value.
For better insight, visit nados.pepcoding.com, post your doubts, community will help you out there.
Sir last mai bikul sahi baat booli aapne great video maja aa gya
kya aap full dekh paae? mujhe 2 din lage ye bnane mei, isko indepth samjhne mei.
@@Pepcoding sir not in 1 sitting but dekh le abb dubara dekhne padega for more better understanding
@@Pepcoding sir jab maths coding mai aa jaati hai uska alag swaad aata hai
Finally sir I have gathered motivation to watch this 1 hr 40 mins long video😅
All the best
east ho ya west sumeet sir is the best
keep motivating, keep learning and keep loving Pepcoding😊
Bhaiya, thanks a lot, for in depth analysis,
small request: Level up me DP ke lectures, proper order me sorted nahi he, dependency wise,
matric multiplication is kept before it's dependent and same for next 5-6 lectures.
Sir puri video deki.... Its worth it !!!
Glad to hear that
Wow explanation hai sir. Thank You!!!
I hope you watched it completely.
@@Pepcoding Haanji complete dekhi Sir
We have to add this line after the final if else case in line 63 ,
to avoid negative answer due to very large numbers.
// when number is very large , it could overflow and change from a large positive number to
// negative number , that's why are taking mod of 1000000007 everytime to keep it in this range
// for negative case and very big numbers
dp[i][j] = dp[i][j] < 0 ? dp[i][j] + 1000000007 : dp[i][j] % 1000000007;
aise hi question ke liye open kri thi video length dekh kr hi moral down hogya ni to me at least 30 mint tk to approach sochta hi hu or ho bhi jata hai kaafi ya pura but isme hmmt si nhi hui sidha puri video hi dekhna shuru krdi.
btw Sir great efforts for recording it. Thank you so much again .
I hope aapne poora dekha aur sab kuch samjha
@@Pepcoding just abhi complete kri hai video do part me dekhi first part me what,how or second part abhi dekh hai . bdhia insight bn gyi Inclusive Exclusice Principle pr based hai proof.
sir please apne videos par ads ON kar lo
The best video till date, so much effort and care showing in the explanation, Loved it sir. keep going!!
mza aya na? Kya aap end tak dekh paai?
@@Pepcoding Yesss bahut amazing tha
Damn what a deep explanation sir
🙌🙌 hats off to uh
thanks a lot sir for your hardwork. is there any possibility for english lectures in the future?
not in near future but next year mid, i will try
Lost you at 1:16:00 ? How is s4 and s1 both x? isnt s4 something like a(x)? Also how is 2x+a+aa = 2x+2?
(a + aa) are two distinct count and same for s1 for s4
@pepcoding please reply?
Pichhla question bohot sahi samjhaya tha
to usi ki wajah se iska why khud hi figure out kar liya
Sir, haven't watched it yet. But will watch for sure, when I'll start DP.
Best of luck
@@Pepcoding Sure Sir. Just keep blessing us with your super content.
superb explanation 100mins spent right 🤩
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 )
Sir, agr ye last k 2 formulae hum interview me bhi aise hi btade to chlega na?
I was so close to banging my head then i remembered Sumeet bhaiya!!!
Haha...keep remembering like this.😋
Are u kidding me bs ek question ke liye almost 2 hr ki video 😂😂
Dekh ke dekho
nice explanation
In the last case where there is two "a" in between the string. How the set s4 is converted to s1? Because after deletion of aa from s4 there is still "a" present at the first and last position of the string present in set s4
For better experience and precisely arranged content you can visit on nados.io, even you can resolve all your doubts by posting all your doubts on community tab of NADOS.
is it just me or the medium level questions are the real hard questions.
yes they really are ,if you haven't done your revision well ( means you hadn't understood some similar questions beforehand ) , then it's too difficult to think on the time of coding round
@@mickyman753 Revison well then it is hard or easy to think on coding round?
@@KejriwalBhakt missed a "haven't"
@@KejriwalBhakt easy ofc
Maza a gaya🔥👌
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 )
Sir dp on trees and burst balloons wale problems also
Burst baloon aj dalega. DP on trees to trees ke sath aaega.
FIRST VIDEO I HAVE SEEN WITH 0 DISLIKES :))
Many more you'll get to see like this😋
Keep learning and keep loving Pepcoding!😊
Now it's 3 dislike
Sir rank list dalvadijea site par🙏🙏
hanji, jald waapis aaegi.
@@Pepcoding are these pre-recorded?
yes
How to figure out the cases - equality and inequality
Sir one more thing i want to know will dsa course on your website will come on UA-cam?
yes all the dsa paid courses will be made free on youtube. it is taking some time. oct 30 is my deadline.
@@Pepcoding u r doing great service to the students . May god bless u always
sir banye badi video dekhne ke liya hum hai
I hope aapne poori dekhi
sir its giving negative result if string size becomes large
answer integer range ke bahar jaa raha hoga
Sir how to explain it in interview?
sir online round k liye bhi pepcoding or leetcode sahi hai ya fir uske liye cp krni hogi
level2 of pepcoding will be enough except for a few companies (tower research, codenation etc.)
sir your code failed for this string "aaaa" on Leetcode (Expected answer : 4 distinct palindromes , but it gives us '2').
when extremes are same and 2'a are also present but m' - middle part not present.
In this case next[i] > prev[j] .... so dp[next[i] +1][prev[j] - 1] (i.e lower triangular value) has garbage value.... which shows error.
Just slight modification
// 2*middle part - m'
//dp[i][j] = 2*dp[i+1][j-1] - dp[next[i] + 1][prev[j] - 1];
int a = 2*dp[i+1][j-1];
if(next[i]+1
Sir ek question baacha hai list me please vo sbse phele complete kra do *Min Squares* wala.
wo to done hai. playlist mei video hai uski. LIS jaisa hai.
great job on proving the equation, but mujhe lagta hai no one can come up with this in an interview. Agar dekh bhi liya to bhi samjhana interviewer ko bahot mushik hai.
keep motivating, keep learning and keep loving Pepcoding😊
ye bs coding round mat aah skta hai with some language change as a hard question
Patth gyi, par dard ache h
arey arey!! tum isse strong ho
Kudos ! Great Job!
you need to watch this twice to understand it completely !!
Sir c++ mein kyu nhi daalte aap solution sirf java kyu sir :( :( Sir aap bhot accha pdhate ho
beta iska solution nikal rhe hain
Java and C++ are almost identical at least from DSA point of view.