Minimum ASCII Delete Sum for Two Strings | INTUITIVE | Recursion | Memoization | Leetcode-712

  Рет қаралды 4,062

codestorywithMIK

codestorywithMIK

Күн бұрын

Пікірлер: 114
@sonumondal9376
@sonumondal9376 Жыл бұрын
Sir following your videos of dp for 2 weeks finally able to solve a problem on my own thanks sir ❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤.... Lots of love from my side
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you so much. I am so happy for this. Pinned your comment 😇🙏 Made my day
@sonumondal9376
@sonumondal9376 Жыл бұрын
Sir following your videos I learnt 2 things how to think a prblm and how to break it into smaller ones so that i can approach a problem part by part 🫂🫂💝
@sonumondal9376
@sonumondal9376 Жыл бұрын
@@codestorywithMIK thanks to you sir a student who won't able to approach a simple dp problem to this stage that he can approach and code the story 🫂🫂💝💝
@codestorywithMIK
@codestorywithMIK Жыл бұрын
❤️❤️❤️
@anuppatankar4294
@anuppatankar4294 Жыл бұрын
Great Video 👌🏻 Solved it myself
@codestorywithMIK
@codestorywithMIK Жыл бұрын
So glad to know 😇❤️
@darshandesale
@darshandesale Жыл бұрын
Ajj mene apne app code likh diya bhaiya Month ka last din improvement ke sath thanks bhaiya I am your Jabra Fan
@codestorywithMIK
@codestorywithMIK Жыл бұрын
So glad to hear that. Thank you so much and congratulations 🎉🎉 We all will rock. Keep the consistency 💪💪
@aadil4236
@aadil4236 Жыл бұрын
I'm liking the video so the Algo picks it up and suggests the video to other learners.
@codestorywithMIK
@codestorywithMIK Жыл бұрын
It means a lot 😇❤️🙏
@tushargupta1711
@tushargupta1711 Жыл бұрын
Aap ki wajhe se hard question below medium lagte h and medium to aab aaisa lagta h dekh k bana lunga m Thxx bhaiya ❤️
@codestorywithMIK
@codestorywithMIK Жыл бұрын
You made my day. Thank you so much Tushar ❤️❤️
@fr4nkyyy720
@fr4nkyyy720 Ай бұрын
ThankYou bhaiyaa , very helpfull and informative video
@turing_machine544
@turing_machine544 Жыл бұрын
I am able to solve the similar question in description by my own in just one go. That's the power of your explanation. You really made Dynamic programming so easy .Before I found you I used to just remember the tabulation formats of code , but watching your recursion and memorization really helps me to understand the way DP works and it helps t build my logic.. Thank you MIK bhaiya...
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Wow. You made my day. Thank you so so much ❤️❤️❤️❤️
@jagratgupta8392
@jagratgupta8392 Жыл бұрын
The Tree Method is very good ....I will try to implement it in dp problems on my own.. thank u sir very great explaination
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you 😇🙏❤️
@wakeuppeggy
@wakeuppeggy Жыл бұрын
Thank You so much Mikky bhai dil se❤❤❤❤❤❤
@vivekpatidar3688
@vivekpatidar3688 Жыл бұрын
Really Very Very great explaination sir , Everyday I watch your videos and complete my Leetcode POTD , You are amazing and very good explainer , you are true that we never regret vising your channel.
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you so much Vivek ❤️
@floatingpoint7629
@floatingpoint7629 Жыл бұрын
thanks for the video.i had solved edit distance before so i was able to figure out 80% of the soln but your video made it 100% clear, and i am only doing daily challenge because of your videos otherwise i would have quit long time ago. thanks again for all the hard work and dedication
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you so much 😇❤️🙏
@riyakansal3312
@riyakansal3312 Жыл бұрын
Got my July batch, thanks for ur efforts sir, I have been able to maintain consistency for 6 months and counting...
@codestorywithMIK
@codestorywithMIK Жыл бұрын
This is wonderful. Congratulations 😇🙏
@SmokyBigSmoke
@SmokyBigSmoke Жыл бұрын
Amazing explanation as always. Thank you so much.
@codestorywithMIK
@codestorywithMIK Жыл бұрын
😇❤️🙏
@codeandtalk6
@codeandtalk6 Жыл бұрын
Solved on own ❤❤❤
@mohithadiyal6083
@mohithadiyal6083 Жыл бұрын
Amazing as ever
@ugcwithaddi
@ugcwithaddi Жыл бұрын
Now i am gaining confidence in Medium qns from your channel. Thanks a lot Hard coming soon
@muditkhanna8164
@muditkhanna8164 Жыл бұрын
i could understand questions very easily and solve them after explanation, but in leetcode contest, i couldn't do the same, i have watched some of your videos and you kind of give me confidence i did solved 2 problems in today's contest. this is what i say improvement.
@codestorywithMIK
@codestorywithMIK Жыл бұрын
So happy to hear this 🙏😇
@shrutishreya7773
@shrutishreya7773 Жыл бұрын
saviour 🙏
@codestorywithMIK
@codestorywithMIK Жыл бұрын
It means a lot 😇🙏
@ravikumarpal1656
@ravikumarpal1656 Жыл бұрын
Your explanation style and simple solution of problem so i become fan of you
@codestorywithMIK
@codestorywithMIK Жыл бұрын
It means a lot Ravi. Thank you so much 😇❤️🙏
@vineettanwar-x4d
@vineettanwar-x4d Жыл бұрын
Thank you sir
@umeshbisht1054
@umeshbisht1054 Жыл бұрын
Thanks a lot bhaiya ❤
@danishsinghjamwal627
@danishsinghjamwal627 Жыл бұрын
one more awesome video
@codestorywithMIK
@codestorywithMIK Жыл бұрын
❤️😇🙏
@sauravchandra10
@sauravchandra10 Жыл бұрын
Got my first leetcode badge today and your videos helped me immensely to stay consistent.
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Awesome Congratulations 😇 And thank you ❤️😇
@oqant0424
@oqant0424 Жыл бұрын
Thank u so much bhaiya :)
@sachinmohanty4577
@sachinmohanty4577 Жыл бұрын
🎉 thank you ❤
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you 😇🙏❤️
@Rajdweep
@Rajdweep Жыл бұрын
pehli bae monthly badge mila all thanks to you bro😁
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Congratulations 😇🙏 Always remember, this is just the beginning, we all are going to get far and grow more ❤️❤️
@Rajdweep
@Rajdweep Жыл бұрын
@@codestorywithMIK thank you bro and yeah a long way to go 😌
@AyushRaj-we2og
@AyushRaj-we2og Жыл бұрын
Big Big salute to you!! MIK bhaiya, your channel is gonna grow exponentially!
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you so much 😇❤️🙏
@sauravbiswajit8091
@sauravbiswajit8091 Жыл бұрын
Thankkkssss again😊
@codestorywithMIK
@codestorywithMIK Жыл бұрын
❤️❤️
@adarshdhital007
@adarshdhital007 Жыл бұрын
Love your videos bro ,don't stop posting videos please!
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Means a lot 😇🙏❤️ Sureee
@saurabhtiwari9614
@saurabhtiwari9614 Жыл бұрын
My implementation - Just calculate lCS and subtract from total of s1 and s2. Why itna taam zhaam🎉🎉🎉
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you so much for sharing Saurabh ❤️❤️ Actually I haven’t yet taught LCS, thats why I didn’t discuss this. I am so glad you shared and tried this approach on your own 😇👍🏻
@saurabhtiwari9614
@saurabhtiwari9614 Жыл бұрын
@@codestorywithMIK thank u soo soo much sir. All thank to u and striver bhayiya
@codestorywithMIK
@codestorywithMIK Жыл бұрын
😇🙏
@souravkumar7612
@souravkumar7612 Жыл бұрын
solved already but just here to support and see new kind of approach😄
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you so much Sourav 😇❤️
@MounikaEMB
@MounikaEMB Жыл бұрын
Simple and great explanation 👏😊
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you so much 😇
@SanskarGarg
@SanskarGarg Жыл бұрын
Solved just after getting a hint from tree diagram and even with a slight change in my base cases. class Solution { public: int f(int i , int j , string &s1 , string &s2 , vector &dp){ // base case if(i == s1.size() and j == s2.size()){ return 0; // no more charcters left } // s2 is not empty to remove all the remaining elements from j to end if(i == s1.size()){ int sum = 0; for(int x = j ; x
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Nailed it 🔥🔥🙏😇❤️
@dayashankarlakhotia4943
@dayashankarlakhotia4943 Жыл бұрын
Lcs pattern. Understood thanks
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you 😇🙏 More coming in DP concepts playlist soon
@beinghappy9223
@beinghappy9223 Жыл бұрын
Video starts from 4:02
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Thank you for providing the pointer 😇🙏
@satyasanjay1339
@satyasanjay1339 Жыл бұрын
I thought of reducing the recursion stack space that's why I used the while loop for two of the edge cases when any one of the strings goes out of bounds. Am I thinking wrong or right? *Java Code:* class Solution { public int minimumDeleteSum(String s1, String s2) { int[][] dp = new int[s1.length()+1][s2.length()+1]; for(int[] row: dp){ Arrays.fill(row, -1); } return solve(0, 0, s1, s2, dp); } int solve(int i, int j, String s1, String s2, int[][] dp){ if(i == s1.length() && j == s2.length()){ return 0; } if(i == s1.length()){ int ans = 0; while(j < s2.length()){ ans += s2.charAt(j); j++; } return ans; } if(j == s2.length()){ int ans = 0; while(i < s1.length()){ ans += s1.charAt(i); i++; } return ans; } if(dp[i][j] != -1) return dp[i][j]; if(s1.charAt(i) != s2.charAt(j)){ //Either we delete ith character or we delete jth char int ans1 = s1.charAt(i) + solve(i+1, j, s1, s2, dp); int ans2 = s2.charAt(j) + solve(i, j+1, s1, s2, dp); return dp[i][j] = Math.min(ans1, ans2); } return dp[i][j] = solve(i+1, j+1, s1, s2, dp); } }
@codestorywithMIK
@codestorywithMIK Жыл бұрын
👍🏻👍🏻❤️
@mileshsoni5016
@mileshsoni5016 Жыл бұрын
we need a dsa sheet for improving dsa by MIK :)
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Soon 😇❤️🙏
@shilpiagrawal3314
@shilpiagrawal3314 8 ай бұрын
Great Video. Will you be posting Bottom Up approach soon?
@aadil4236
@aadil4236 Жыл бұрын
I directly searched for your video because the yesterday's explanation was so good!! How did you become so good? I mean did you read any book on dp? I want to solve problems like you. Any advice will be appreciated 😄😄
@codestorywithMIK
@codestorywithMIK Жыл бұрын
It means a lot to me 😇❤️🙏🙏 I will soon create a video ok how to properly study dsa with good road map.
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Also, i am just like you guys. Learning everyday. We all are on same platform, we all will learn together, we all will rise together ❤️❤️
@ManojKrVerma-vw4dx
@ManojKrVerma-vw4dx Жыл бұрын
Have u made videos on dp with bitmasking ?
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Not yet. They will come on “DP concepts & Qns” playlist
@AshutoshChoudhary2004
@AshutoshChoudhary2004 Жыл бұрын
Please solve Leetcode 1349. Maximum Students Taking Exam it is also s a DP question
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Sure thing. Noted
@Raj10185
@Raj10185 Жыл бұрын
my implementation :- int n1 , n2; int dp[1002][1002]; int solve(int i , int j , string & s1 , string & s2) { if(i
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Surely noted. LIS going to start today/tomorrow Then, will cover LCS and variants
@xiaoshen194
@xiaoshen194 Жыл бұрын
I passed string but forgot to pass it by reference. Got so many MLEs 😅
@awkward_adi
@awkward_adi Жыл бұрын
Same case with me
@danianiazi8229
@danianiazi8229 Жыл бұрын
Is there any playlist from compelte basic all topics
@codestorywithMIK
@codestorywithMIK Жыл бұрын
In my playlist section, you will notice that i create two playlists for each topic 1) One playlist for Popular Interview Qns 2) One playlist for Concepts of the topic For example : Graph Popular interview qns, Graph Concepts playlist, Similar for DP also. Similarly I will create concepts playlist for all topics soon
@danianiazi8229
@danianiazi8229 Жыл бұрын
@@codestorywithMIK Thanks Sir. I appreciate. Its a long journey and I'm still beginner hopping to learn many thing from you
@himanshigoel7510
@himanshigoel7510 Жыл бұрын
sir its a request , please make videos on contest questions also
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Very soon. Currently very difficult with available bandwidth ❤️❤️
@ashutosh61290
@ashutosh61290 Жыл бұрын
class Solution { public: int m, n; int solve(int i, int j, string &s1, string &s2, vector &dp){ if(i>=m && j>=n){ return 0; } if(dp[i][j]!=-1){ return dp[i][j]; } if(i>=m){ return dp[i][j] = s2[j] + solve(i, j+1, s1, s2, dp); } else if(j>=n){ return dp[i][j] = s1[i] + solve(i+1, j, s1, s2, dp); } if(s1[i]==s2[j]){ return dp[i][j] = solve(i+1, j+1, s1, s2, dp); } //two possibility int delete_s1_i = s1[i] + solve(i+1, j, s1, s2, dp); int delete_s2_j = s2[j] + solve(i, j+1, s1, s2, dp); return dp[i][j] = min(delete_s1_i, delete_s2_j); } int minimumDeleteSum(string s1, string s2) { m=s1.size(); n=s2.size(); vector dp( m+1 , vector (n+1, -1)); return solve(0, 0, s1, s2, dp); } };
@kumariranjanayadav4652
@kumariranjanayadav4652 Жыл бұрын
bhaiya gfg ka bhi krwa dia kro n
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Very soon. Will start covering that
@jagadeshwaranar3553
@jagadeshwaranar3553 Жыл бұрын
Bro, can you open the slots in topmate today..I would like to book a session ??
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Hi there, Unfortunately, it’s blocked due to my unavailability for few coming days. However, i will soon share a form where multiple people can join for a webinar . 🙏🙏
@molyoxide8358
@molyoxide8358 Жыл бұрын
Bro can you provide me the correct link of your DP playlist?
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Hi there, DP Concepts & Qns Playlist - kzbin.info/aero/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt DP popular Interview Qns - kzbin.info/aero/PLpIkg8OmuX-L_QqcKB5abYynQbonaNcq3
@DurgaShiva7574
@DurgaShiva7574 Жыл бұрын
if the GOD of DSA had a face, it will be surely you.
@anushkathakur6531
@anushkathakur6531 Жыл бұрын
DOUBT ..... bhaiya,isme aapne 1st base case ke just neeche "already calculated hai ya nhi / memoization array" vala check lagaya if(t[ i ][ j ] != -1) return t[ i ][ j ]; , par vo 2nd aur 3rd base cases ke pehle lagaya hai, toh kaise pata chalta hai ki kis base case se pehle lagana valid hai...? Kyonki PREDICT THE WINNER vale mein maine check base case ke pehle laga diya tha toh vo kuch OUT OF BOUNDS ki ERROR de rha tha.....
@codestorywithMIK
@codestorywithMIK Жыл бұрын
No no, You can put the check in the beginning as well. Just ensure that , for t[i][j] , i and j should not be out of bound. That’s why we always define size of t a little greater to be on safe side.
@codestorywithMIK
@codestorywithMIK Жыл бұрын
If it gives error, you can increase the size of t.
@dhairyachauhan6622
@dhairyachauhan6622 Жыл бұрын
did this in 10 mins :) CODE: class Solution { public: vectordp; int solve(string &s1,string &s2,int idx1,int idx2){ if(idx1 == 0){ int sum = 0; while(idx2 > 0){ sum += s2[idx2-1]; idx2--; } return sum; } if(idx2 == 0){ int sum = 0; while(idx1> 0){ sum+= s1[idx1-1]; idx1--; } return sum; } if(dp[idx1][idx2] != -1){ return dp[idx1][idx2]; } if(s1[idx1-1] == s2[idx2-1]){ int pick = solve(s1,s2,idx1-1,idx2-1); return dp[idx1][idx2] = pick; } else{ int take1 = s1[idx1-1] + solve(s1,s2,idx1-1,idx2); int take2 = s2[idx2-1] + solve(s1,s2,idx1,idx2-1); return dp[idx1][idx2]= min(take1,take2); } return 0; } int minimumDeleteSum(string s1, string s2) { int n = s1.length(); int m = s2.length(); dp.resize(n+1,vector(m+1,-1)); return solve(s1,s2,n,m); } };
@codestorywithMIK
@codestorywithMIK Жыл бұрын
🔥🔥🔥
@bhartipatel7833
@bhartipatel7833 Жыл бұрын
If constraint length is 1000 why we use dp array of size 1001 ?
@codestorywithMIK
@codestorywithMIK Жыл бұрын
That’s for being on safe side so that we don’t go out of bound 😇 Always do +1 for safe side. More coming in DP concepts playlist soon
@footballcreativeeverywhere260
@footballcreativeeverywhere260 Жыл бұрын
Bhai recursion nahi hota bhai kya karu😔
@codestorywithMIK
@codestorywithMIK Жыл бұрын
Hi there, Have you followed any Recursion playlist from anywhere ? I might plan to create one in my channel soon
@swayamterode4965
@swayamterode4965 Жыл бұрын
Sir yek doubt tha yeh kese pata krte hai ki Memo lagega constraints ko dekh k hi? Mei figure out hi nahi kr pata kab lagega kab nahi!
@shriyanshjain4444
@shriyanshjain4444 Жыл бұрын
CAN ANYONE TELL ME WHAT AM I DOING WRONG? class Solution { public: string lcs(string s1, string s2, vector &dp, int lcslen){ string lcsstring = ""; int index = lcslen-1; for(int i =0; i < lcslen; ++i) lcsstring += '#'; int i = s1.size(), j = s2.size(); while(i > 0 && j > 0){ if(s1[i-1] == s2[j-1]){ lcsstring[index] = s1[i-1]; index--; i--; j--; }else{ if(dp[i-1][j] > dp[i][j-1]){ i--; }else if(dp[i-1][j] < dp[i][j-1]){ j--; }else{ if(s1[i] < s2[j]){ i--; }else{ j--; } } } } return lcsstring; } int populatedp(string s1, string s2, vector &dp) { int n1 = s1.size(), n2 = s2.size(); for(int i = 0; i
@Abhi_008
@Abhi_008 Жыл бұрын
Anyone Please help?? I don't know where I'm doing wrong. Space Optimization not working fine. first testcase where it fails -> s1 = ""ccaccjp" s2 ="fwosarcwge" class Solution { int solveRec_Mem(string& s1, string& s2, int i, int j, vector& dp) { int m = s1.length(); int n = s2.length(); if(i >= m && j >= n) return 0; if(j >= n) // string s2 over return s1[i] + solveRec_Mem(s1, s2, i+1, j, dp); if(i >= m) // string s1 over return s2[j] + solveRec_Mem(s1, s2, i, j+1, dp); if(s1[i] == s2[j]) return solveRec_Mem(s1, s2, i+1, j+1, dp); if(dp[i][j] != -1) return dp[i][j]; // Two Options int delete_i = s1[i] + solveRec_Mem(s1, s2, i+1, j, dp); int delete_j = s2[j] + solveRec_Mem(s1, s2, i, j+1, dp); return dp[i][j] = min(delete_i, delete_j); } int solveTab(string& s1, string& s2) { int m = s1.length(); int n = s2.length(); vector dp(m+1, vector(n+1, 0)); // Analyze base cases for(int i = m-1; i >= 0; i--) { // string s2 over dp[i][n] = s1[i] + dp[i+1][n]; } for(int j = n-1; j >= 0; j--) { // string s1 over dp[m][j] = s2[j] + dp[m][j+1]; } for(int i = m-1; i >= 0; i--) { for(int j = n-1; j >=0; j--) { if(s1[i] == s2[j]) { dp[i][j] = dp[i+1][j+1]; } else { int delete_i = s1[i] + dp[i+1][j]; int delete_j = s2[j] + dp[i][j+1]; dp[i][j] = min(delete_i, delete_j); } } } return dp[0][0]; } int solveSO(string& s1, string& s2) { int m = s1.length(); int n = s2.length(); vector curr(n+1, 0); vector next(n+1, 0); // Analyze base cases for(int i=0; i= 0; i--) { for(int j = n-1; j >=0; j--) { if(s1[i] == s2[j]) { curr[j] = next[j+1]; } else { int delete_i = s1[i] + next[j]; int delete_j = s2[j] + curr[j+1]; curr[j] = min(delete_i, delete_j); } } next = curr; } return next[0]; } public: int minimumDeleteSum(string s1, string s2) { // Recursion + Memoization // int m = s1.length(); // int n = s2.length(); // vector dp(m, vector(n, -1)); // return solveRec_Mem(s1, s2, 0, 0, dp); // // Tabulation // return solveTab(s1, s2); // Space Optimization -> not working on all testcases. return solveSO(s1, s2); } };
@yatri6329
@yatri6329 Жыл бұрын
Ye DP ke kon sa pattern me fall krega?
@codestorywithMIK
@codestorywithMIK Жыл бұрын
String DP. LCS variants
@yatri6329
@yatri6329 Жыл бұрын
​@@codestorywithMIKDP & Graph always show me tough time.
@souravjoshi2293
@souravjoshi2293 Жыл бұрын
@@yatri6329 Trust me, I also had this same problem and when I followed his Graph Concepts playlist, today I am able to solve tough topics like Dijkstra, Prims , Kosaraju also etc. All are so intuitive that I still remember what was taught
@codestorywithMIK
@codestorywithMIK Жыл бұрын
You can try my Graph Concepts playlist It will help for sure 😇🙏
За кого болели?😂
00:18
МЯТНАЯ ФАНТА
Рет қаралды 3,2 МЛН
How Many Balloons To Make A Store Fly?
00:22
MrBeast
Рет қаралды 149 МЛН
Dynamic Programming isn't too hard. You just don't know what it is.
22:31
DecodingIntuition
Рет қаралды 199 М.
Leetcode 712 Minimum ASCII Delete Sum for Two Strings
11:24
Jeevan Kumar
Рет қаралды 1,5 М.