Interleaving String | Khandaani Tareeka | Memoization | GOOGLE | Leetcode-97

[@iamnoob7593]

brilliant explanation , Out of the world - All powerful DSA

[@mohdalizilani9896]

"Your explanation is simply exceptional! I haven't come across a video that explains every step so clearly and logically. Your approach truly resonates with my understanding of why each step is essential to solve this problem. Kudos, sir, for your outstanding clarity and insight!"

[@codestorywithMIK]

Your comment made my day. Thank you so much ❤️❤️🙏🙏😇😇

[@JoyAcharyatvl]

Tnanks . I have solved 90% without watching your video. I take help from your video last 10%. But the credit is youers because I have learned solving dp problems watching your previous video. Thnaks Again. As usual , your video is always best.

[@codestorywithMIK]

You are most welcome ❤️😇🙏

[@anuppatankar4294]

Watching your videos always helps me to learn new things. I solved it myself using 3 variables still come here to watch your video and then realise it can be solved using 2D dp too . Great Video 🔥

[@codestorywithMIK]

Thank you 😇❤️🙏

[@unknown47896]

same here bro

[@AlishaKhan-ww3io]

Because of you I have been now able to solve DP problems. Thanks a lot

[@tutuimam3381]

Amazing explanation🌹🌹

[@aman3210]

mst smjh aya bhaiyaa ... dp smjh aane lgi abb thanks++ ; thanks =25;

[@xiaoshen194]

Thnx. Although khud se kr liya, initially bahut WA aye due to 2 pointer. But samajh gya Ki dp lagegi

[@percyx29]

i am in love with these lectures

[@codestorywithMIK]

Means a lot. Thank you ❤️😇

[@MounikaEMB]

Simple and clear explanation Thank you😊

[@floatingpoint7629]

the best explanation. no one explains dp better then you

[@codestorywithMIK]

Means a lot 😇❤️🙏

[@dhairyachauhan6622]

I did with 3 variables then saw solution using 2. I knew this video will be explaining it for sure :p love how you always make recursion tree

[@codestorywithMIK]

😇🙏

[@kaukuntlaprudviraj108]

as usual assome explanation that was really mind blowing , figuring out that i==n and j==m and k==N at same time for to satisfy given condition is not so simple , making such an idea will be difficult , remaining is as usual easy Thanks

[@codestorywithMIK]

Thank you 😇❤️🙏

[@unknown47896]

solved this question on my own using 3 variables bcoz of u bro...tq for everything my code: class Solution { public: int dp[101][101][201]; bool solve(int i,int j,int k,string& s1,string& s2,string &s3,int n1,int n2,int n3) { if(i==n1 && j==n2 && k==n3) return true; if(i>=n1 ) { if(s2[j]==s3[k]) return dp[i][j][k]=solve(i,j+1,k+1,s1,s2,s3,n1,n2,n3); } if(j>=n2 ) { if(s1[i]==s3[k]) return dp[i][j][k]=solve(i+1,j,k+1,s1,s2,s3,n1,n2,n3); } if(dp[i][j][k]!=-1) return dp[i][j][k]; bool ans=false; if(s1[i]==s2[j] && s2[j]==s3[k]) { ans|= solve(i,j+1,k+1,s1,s2,s3,n1,n2,n3); ans|= solve(i+1,j,k+1,s1,s2,s3,n1,n2,n3); } else if(s1[i]==s3[k]) { ans|= solve(i+1,j,k+1,s1,s2,s3,n1,n2,n3); } else if(s2[j]==s3[k]) { ans|= solve(i,j+1,k+1,s1,s2,s3,n1,n2,n3); } return dp[i][j][k]= ans; } bool isInterleave(string s1, string s2, string s3) { int n1=s1.size(); int n2=s2.size(); int n3=s3.size(); if(n1+n2!=n3) return false; memset(dp,-1,sizeof(dp)); return solve(0,0,0,s1,s2,s3,n1,n2,n3); } };

[@SurajkumarYadav-ig1ss]

Best as usual

[@sonumondal9376]

Sir after a long time i am commenting nice one sir ❤❤ since i learnt dp concepts from you j was able to solve the problem in m*n*N but you as my guru made it to m*n ❤❤❤❤ keep going sir!!

[@codestorywithMIK]

Thank you so much ❤️😇

[@dayashankarlakhotia4943]

Good explanation i am requesting to you that tabulation approach explanation with memorization so we understood very well and also space optimization will explain many fang companies also require space optimization code because compilation is so tough for interviews

[@codestorywithMIK]

Will upload soon 👍🏻😇

[@rohanchoudhary5523]

Hey , Mik Can U please Try Leetcode Contest Explanation of Questions That would be very helpful

[@prachuryapransarma]

yeah that will be great

[@wearevacationuncoverers]

love the way how you make things look so easy. Thanks a lot for making DP easy for me

[@dayashankarlakhotia4943]

Tc=0(n*m); Sc=0(n*m); space optimization. Tc=0(n*m); Sc=min(n*m); m=s1.length. m=s2.length.

[@sauravchandra10]

Clearly explained, thanks !

[@codestorywithMIK]

Glad it was helpful!

[@jagratgupta8392]

very nice explanation

[@honey6567]

this is best ever ....🤩🤩🤩🤩🤩

[@rishabh2349]

bhaiya i have one question if let suppose one string is exhausted for example i==s1.size() but still s2 and s3 are remaining then dont you think if we will access s1[i] it should give runtime error because we are calling an index which is out of bounds? I mean to say we should write a check if i

[@rishabh2349]

I think if we dont add this condition then the code will fail on these test case: s1="hijk" s2="lmno" s3="hijklmno"

[@codestorywithMIK]

@@rishabh2349 Ah yes yes, For Java, you MUST add that check (C++ handles the out of bound case) I have added this info in subtitles as well for others. Thanks a lot Rishabh ❤

[@dayashankarlakhotia4943]

Memorization code. class solution { Public boolean solve (string s1,string s2,string s3,int I,int j,int [][]dp){ if(i+j)==s3.length() return true; if(dp[i][j]!=-1)return dp[i][j]==1; boolean ans=false; if(i

[@cacklouncle]

@@codestorywithMIKcan you please tell how C++ handle out of bound case, doesn't it give error?

[@thekindspill]

Super clear and crystal clear explanation as always

[@K_EC_rahulsharma]

isn't j is already in out of bound if s2 is empty ,bhaiya?

[@nishkamvarshney2368]

i have checked with different test cases ...they are treating empty strings concatenation possible to make s3..as empty string can be placed anywhere in between the other non-empty string.

[@codestorywithMIK]

s1 = “aab” s2 = “” s3 = “aab” Answer is False because we can’t take anything this from s2 to concatenate with s1 to make s3

[@invinishku1542]

@@codestorywithMIK bro check again with your testcase only.... it's giving true.... that's what i am saying....your this conclusion is wrong.

[@umeshbisht1054]

Thanku bhaiya ❤

[@RahulGuptaa29]

Doubt!! Why did they mentioned "|n - m|

[@codestorywithMIK]

Thanks a lot 😇🙏 This actually is mentioned just to confirm that we MUST have substrings from both strings. Note that m and n here in the problem description means number of substrings of s1 and s2. Example- s1 = “aab” s2 = “” s3 = “aab” Output - False Even if we can concatenate s1 with s2 here to get s3 but it’s not correct because we Must have substrings from both s1 and s2

[@RahulGuptaa29]

@@codestorywithMIK sir but in above example the leetcode compiler returns true and it is right? As our first condition hits from the solution. If(i==m && j==n && k==N) return true; Here m = 3, n=0, N = 3 and even after dry run it returns true. But it will return false if input was s1 = "abc" s2 = " " s3 = "abc" But in constraints it is given that s1 s2 and s3 are lowercase letters.

[@AmarjeetKumar-to9ub]

Thank You :)

[@codestorywithMIK]

You're welcome! 😇

[@Engineer_With_A_Life]

Amazing explanation. Could you tell which tool you use as whiteboard in your videos?

[@prachuryapransarma]

apple notes

[@abhinay.k]

thank you

[@SanskarGarg]

A subtle different approach: class Solution { public: bool f(int i , int j ,string &s1, string &s2, string &s3 , vector &dp){ int k = (i+j); if(i == s1.size() and j == s2.size() and k == s3.size()) return true; if(dp[i][j] != -1) return dp[i][j]; bool ans = false; // if k th charcater of s3 matches with both the s1 and s2 if(s3[k] == s1[i] and s3[k] == s2[j]){ ans = f(i+1 , j,s1,s2,s3,dp) or f(i , j+1,s1,s2,s3,dp); } // only matches with s1 else if(s3[k] == s1[i]){ ans = f(i+1 , j ,s1,s2,s3,dp); } // only matches with s2 else if(s3[k] == s2[j]){ ans = f(i , j+1 ,s1,s2,s3,dp); } return dp[i][j] = ans; } bool isInterleave(string s1, string s2, string s3) { if(s1 == "" and s2 == "" and s3 == "") return true; int a = s1.size(); int b = s2.size(); int n = s3.size(); if(n != a + b) return false; vector dp(a+1 , vector(b+1,-1)); return f(0 , 0 , s1 , s2 , s3,dp); } };

[@shashwatchawla]

i am surprised why his code runs without this condition if(s3[k] == s1[i] and s3[k] == s2[j]){ ans = f(i+1 , j,s1,s2,s3,dp) or f(i , j+1,s1,s2,s3,dp); }

[@gauravpunia4527]

bhaiya gfg pe same problem h but usme as briefly nhi bta rkha ki what is the meaning of interleaving so agar general case lege chle where c = "efghi" a = "abcefabvd" b = "deghiaas" here at the starting state it return false does not explroe all the paths

[@codestorywithMIK]

iPad PDF Notes - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-97-Interleaving%20String.pdf ************************************ JAVA ************************************ class Solution { int m, n, N; Boolean dp[][]; boolean check(String s1, String s2, String s3, int i, int j) { if(i >= m && j >= n && i+j >= N) return true; if(i+j >= N) return false; if(dp[i][j] != null) return dp[i][j]; boolean result = false; if(i < m && s1.charAt(i) == s3.charAt(i+j)){ result = check(s1, s2, s3, i+1, j); } if(result == true){ return dp[i][j] = result; } if(j < n && s2.charAt(j) == s3.charAt(i+j)){ result = check(s1, s2, s3, i, j+1); } return dp[i][j] = result; } public boolean isInterleave(String s1, String s2, String s3) { m = s1.length(); n = s2.length(); N = s3.length(); if(m + n != N) return false; dp = new Boolean[m+1][n+1]; return check(s1, s2, s3, 0, 0); } }

[@rahulmaurya6451]

Bhaiya There is Also a Follow Up in this Ques.. "Follow up: Could you solve it using only O(s2.length) additional memory space ?" How can we do this ?

[@codestorywithMIK]

Hi Rahul, I will surely cover that in my “DP concepts & Qns” playlist. However if you click on my Github Link description, see the Approach- 4 just to get a rough idea ❤️❤️❤️

[@adarshdhital007]

Bro awesome video, now from next time click the new button above the submit button and then solve the question haha.

[@codestorywithMIK]

Sure 😃

[@animesh414]

Sir can you tell me how we can convert our recursion+memo code into iterative dp(bottom-up) or how can we think for bottom up if we know rec+memo solution ,please.

[@codestorywithMIK]

Hi Animesh, I am covering the Recur+Memo and Bottom Up of all DP variants in this playlist - kzbin.info/www/bejne/bZavfoJ7Zs-hotU Hope that will help

[@spandanrastogi7144]

Why it is safe it ignore this condition |n - m|

[@IconOfSeas]

could you tell the O(N) space approach ?

[@arandkarvishal8657]

Bhaiya please upload vedioes of leetcode contest only last two questions of contest ❤

[@codestorywithMIK]

Will soon plan that

[@JosephDavid01]

Bhai tabulation bhi sath me hi samja diya karo

[@Tejaswi-xd4re]

Sir u told to remind about question guidance video

[@codestorywithMIK]

Noted ❤️

[@Tejaswi-xd4re]

@@codestorywithMIK tq sir Will hope that u upload the video soon

[@codestorywithMIK]

Yes it will come tomorrow (sunday) Also, would you like to share what points of guidance are you looking for ? It will help me to add more details in the guidance video

[@Tejaswi-xd4re]

@@codestorywithMIK sir for students who joined btech first year.. We wanna start dsa.. We learn a particular concept for example arrays but in leetcode to solve problems on arrays they all are mixed problems like array+dp, array+recursion etc.. We can't understand which problems to solve after learning theory of particular topic.. As a student who learnt only arrays topic we can't solve questions which use arrays+dp, arrays +recursion etc.. That's the major problem first year students face and no one is guiding about it..

[@Tejaswi-xd4re]

@@codestorywithMIK I hope u can understand sir... I wud like you to guide us which questions to do, what to study etc Tq

[@shashwatchawla]

why you didn't talked about |n - m|

[@codestorywithMIK]

This actually is mentioned just to confirm that we MUST have substrings from both strings. Note that m and n here in the problem description means number of substrings of s1 and s2. Example- s1 = “aab” s2 = “” s3 = “aab” Output - False Even if we can concatenate s1 with s2 here to get s3 but it’s not correct because we Must have substrings from both s1 and s2

[@shashwatchawla]

@@codestorywithMIK if I try to break S1 such that it has 3 parts and S2 such that it has 1 part then we get the diff as 2 but as per this condition we can have a max of 1 diff only , so it is violating the condition but there is definitely a possibility of getting S3 , .....idk if you can understand what i said hahaha, but no issues thanks for the explanation :)

[@deeptiranjan2005]

Still waiting for a session 😊❤... Keep it up.

[@codestorywithMIK]

Very soon! ❤️😇🙏

[@codeandtalk6]

❤❤❤

[@tejaspatel2212]

Waiting for Graph concept and playlist completion 😅😅

[@codestorywithMIK]

Soon completing this 😃

[@hello-sb7zj]

sir if( k>=N ) return false alag se likhne ki kya jrurat h wo upr to likh diya h jb teeno condition lgayi h

[@codestorywithMIK]

There can be a situation that one of the strings was equal to s3. Let's take an example : s1 = "aab" s2 = "" s3 = "aab" In this case, i will become = m and k will become = N but j is empty so first if condition will not be hit. Still k has reached N, which is wrong. So we return false

[@hello-sb7zj]

@@codestorywithMIK thanks sir got it

[@kamleshpatel142]

@@codestorywithMIK Won't if condition hit the case, because i==m, k==N and j==n. As n=0 and j=0. So if there is empty string, it can be said that j is already out of bounds. ????

[@RAHULSHARMA-dl1jc]

Bhai bss ek confusion hai, isme runtime error kyu nhi aarha agar i==n hai aur firm hum condition check kr rhe hai s1[I]==S3[k], please explain bhaiya

[@codestorywithMIK]

Actually in C++ accessing s1[i] will not be issue if i == n , in C++ it will return blank. But in Java or other language it will give runtime error. But always put i

[@RAHULSHARMA-dl1jc]

Thanks bhaiya❤,

[@harikeshsingh93]

Which software you use to teach?

[@honey6567]

sir concept dp me new approch bottom up ka bacha kara do

[@083_h_nitishkumarjha3]

hey mik at 15:44 you said if one string is empty answer is going to be false....... but shouldn't it be true as we can take whole string1 as substring and empty susbtring and interleave them?

[@AlishaKhan-ww3io]

Example : "aabcc" "aabcc" "" This will be false. Because we don't have anything in S2 to concatenate with S1.

[@083_h_nitishkumarjha3]

@@AlishaKhan-ww3io but can't we take empty substring representing a part of s2 as it's also a substring.......... and m-n will be still less than 1

[@083_h_nitishkumarjha3]

update: I was right I tried this case and output should be true, mik did some mistake In explanation

[@rahulmaurya6451]

@@AlishaKhan-ww3io In the Question it is mentioned that "|s1.length() - s2.length()|

[@codestorywithMIK]

@rahulmaurya6451 , in the Qn it's given that |m - n|

[@akhilchauhan9417]

I can't think or build intuition for Bottom Up.

[@dayashankarlakhotia4943]

Public class solution { Public boolean is Interleave (string s1,string s2,string s3){ int m=s1.length (),n=s2.length (),l=s3.length (); if(m+n!=l)return false; boolean []dp=new boolean [n+1]; dp[0]=true; for(int j=1;j

[@aswithasai4015]

actually jab meine Q try kiya i got error for this tcase -> if one string is empty and s1=s3 we should return false because substring of an empty string is empty then what can we concatenate .

[@AlishaKhan-ww3io]

Example : "aabcc" "aabcc" "" This will be false. Because we don't have anything in S2 to concatenate with S1.

[@aswithasai4015]

haa but s1=s3 then we can take all char from s1 and make s3 if we have anything in s2 and we leave it then it will be wrong but if there is empty string then why will it be still a bit confused@@AlishaKhan-ww3io

[@codestorywithMIK]

@@aswithasai4015 Hi there, According the Qn, it's not allowed to leave any string. We have to include all characters from s1 and s2 to form s3. This is the reason the example below returns false: Example : "aabcc" "aabcc" "" Also, one important tip to all - "Always ask such qns during interviews to clear the Qn. It leaves a good impression on the interviewer"

[@aswithasai4015]

@@codestorywithMIK ok sir tq

[@wetubetech49]

But you have not checked |n-m|

[@satyamkumaryadav1560]

i have a doubt what about the condition |n - m|

[@083_h_nitishkumarjha3]

this is because it doesn't matter if you think, we can take substring of any size, and s3. size() == s1. size() + s2. size() so we are bound to include s2 also so that we can cover whole s3 , and let's consider you took 3 substrings of s1 and 1 substring of s2 but when you concatenate them 2 substrings of s1 will combine and act as single 1 so in every case if it is possible to get true we will always get m-n

[@satyamkumaryadav1560]

@@083_h_nitishkumarjha3 thanks bro

[@VIJAYYADAVPCECR]

sir leetcode ki link diya kro jha se hm direct leetcode pr dekh ske Q ko

[@codestorywithMIK]

I always attach the Leetcode link in the description of the video. You can find it there 😇

[@VIJAYYADAVPCECR]

Sir link only redirect to problem not to solution @codestorywithMIK

[@Abhishek-sz8wg]

u didn't think about |n - m|

[@souvikmukherjee8245]

Doubt: if result==true return true. yeh part kyu add kar raha hu samajh me nehi aya

[@codestorywithMIK]

If you got the result true from one way (i.e. taking ith character and exploring further) then there is no point searching for other possibilities . We return as soon as we get true

[@souvikmukherjee8245]

@@codestorywithMIK Okay, now I understand why this line was so necessary 😊. I made a tree with "s1=aabc, s2=abad, and s3=aabcabad" to fully comprehend. We can also use the OR operator as well 👍. Thank you again, Mik, for such an amazing step-by-step explanation 🙏. I am waiting for a recursive problem where for loops is being used . please next time when you will use for loop inside a recursive function explain in a bit detail about how for loop is helping with a tree diagram. I tried to dry run , but it gets really confusing to track that many calls.😕

[@honey6567]

bottom up -> //bottom up dp class Solution { public: vectordp; bool isInterleave(string s1, string s2, string s3) { if(s1.size()+s2.size()!=s3.size())return 0; dp.resize(s1.size()+1,(vector(s2.size()+1,0))); for(int i=0;i=1 && s3[k-1]==s1[i-1] && s3[k-1] == s2[j-1]){ dp[i][j]=dp[i-1][j] || dp[i][j-1]; //ya dp[i-1][j] insert kro ya dp[i][j-1]; ya isko insert kro } else if(i>=1 && s1[i-1] == s3[k-1]) dp[i][j]= dp[i-1][j]; else if(j>=1 && s2[j-1] == s3[k-1]) dp[i][j] = dp[i][j-1]; else dp[i][j]=0; } } return dp[s1.size()][s2.size()]; } };

[@jayminrajgor108]

Khandani template 🚀🚀🚀🚀🚀🚀🚀🚀

[@codestorywithMIK]

😇🔥

[@karanthakur11]

Anybody facing issue like not passing all test cases