Understood and you've completely changed my life. Doesn't matter if I get placed in a good company or not but the quality of this lectures are supreme and I will carry this knowledge for rest of my life.
understood bhaiya!!! after a very long time i am back to your channel....previously i was doing a race that as soon as you upload the video, i should watch it then n there, before the next video gets uploaded in this dp series, but due to some busy schedule, i lost the race. yeah, but your quality and energy is still the same as your starting videos
@@dikshamakkar2850 I have a question , vector dp(n + 1, vector(m + 1,0)); this line of code initializes all index to 0 then why did he ran 2 more loops to initialize some row and column to 0 again?
@@dikshamakkar2850 nah loop isnt required class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n = text1.size(); int m = text2.size(); vectorprev(m+1,0),curr(m+1,0); for(int i=1;i
This was life-changing. Thank you Striver, you taught what paid courses could not for so many years. I wish I had discovered your site earlier; it would have saved so much time and energy.
absolutely minds bogling.i am not kidding i wasn't able to solve simple recusion questions few weeks ago now i can solve medium and hard dp questions on my own without watching videos.all i can say thank you striver.
If someone is using java to write the code, in space optimization approach there will be error in a testcase, to resolve that error replace prev = curr with prev = curr.clone(); or else use the code snippet int [] temp = prev; prev = (curr); curr = temp; Because in java prev = curr will not create a new array but it will point both the references to same address. Your program would work fine.
US ❤ I should mention I am solving DSA consistently from past 1 year. Encountered this question a lot of times. But till date this is the best explanation boss❤
for those who don' t want to use shifting of index in tabulation , they can do it in traditional way using below code. we can discuss if you have any doubts. int longestCommonSubsequence(string text1, string text2) { int n1= text1.size(); int n2= text2.size(); vector dp(n1, vector(n2, -1));
//filling first coloumn of the matrix //say we have text1= bcade and text2=a then //the longest cmmn subsqnce is 0 until index1 reaches 2, once it reaches 2 beyond that lcs =1;
What a brilliant explanation, I come here after watching Aditya Verma's videos on DP but didn't feel the intuition behind the tabulation that he was doing and now I know the thought process all thanks to Striver.
simple space optimization technique : just 2,3 chanes instead of using 2 different vectors we can just change dimension of dp to [no of previous rows we wanred + 1][no of colum] int longestCommonSubsequence(string s1, string s2) { vectordp(2, vector(s2.size()+1, 0)); // changing dimension as per need for(int i=1; i
I solved with different tabulation approach (without shifting index) as below: int m=text1.length(); int n=text2.length(); int[][] dp = new int[m][n]; int temp=0; for(int i=0; i
Believe or not Striver I solved the problem by myself without seeing this video Note : I gone through all your previous dp videos properly with no skip :) I am so happy.. Thanks to you.
Understood!!! Same tabulation method that you taught in previous videos... Same approach without index shifting. Base case in Memoization : if(index1 == 0 || index2 == 0) { return s1.charAt(index1) == s2.charAt(index2) ? 1 : 0; } Tabulation : static int tabulation(int index1, int index2, String s1, String s2) { int[][] dp = new int[s1.length()][s2.length()]; dp[0][0] = s1.charAt(0) == s2.charAt(0) ? 1 : 0; for(int i = 1; i
I’m just so thankful to you for this wonderful series, I’m honestly enjoying it dude, surely you’re one of the best! I even did the problem by myself so easily, i was shocked believing😂
Without right shifting the Indexes, still we could do it as default initialise with 0 and then start from i=0 and j=0 but adding constraints of out of bounds. #include //Tabulation Solution int lcs(string s, string t) { int n1=s.size(); int n2=t.size(); vectordp(n1,vector(n2,0));
If you started new topic like DP on string it is important that you should explain each problem with tabulation method also thoroughly, instead of just writing code, but Great Series.
@@jaykumargupta7307 int longestCommonSubsequence(string s1, string s2) { int n = s1.length(), m = s2.length(); vector cur(m+1, 0); int prev; for(int ind1=1; ind1
if someone doesn't want shifting they can write base case as below idea is to make let say dp[0][i1]=1 and also all further i>i1 equal to 1 eg dp[0][i1+1]=1,dp[0][i1+2]=1,.... similarly for second loop also remember what dp[i][j] represents: ;length of lcs of substring s1[0...i] and s2[0..j] bool b=false; for(int i=0;i
Understood. Only one point, if you are doing the tabulation to eliminate the O(m*n) S.C and then including (m+n) extra space for an extra row and column, it seems a bit redundant.
Understood..! Awesome method "shifting of index" 😁......though without shifting i have solved tabulation, all credits to you only, but shifting of index makes that too easy. Love you ❤
striver help this brother out! how you are staying disicplined? so far you are single ,right? how you are avoiding every distractions and focusing on your goal please make a video on this brother!!
Was able to solve this on Leetcode by myself. Thanks Striver !!! public int longestCommonSubsequence(String s1, String s2) { int n1 = s1.length(),n2 = s2.length(); int[] prev = new int[n2]; //base cases if(s1.charAt(0)==s2.charAt(0)) prev[0]=1; for(int i=1;i
can you please share the code of 1 array optimisation , my 1 array code giving me wrong answer on leetcode testcase 23 , i saw a solution where someone uses 2 extra variables to do in 1 array. plz reply
pro tip -> use right shift method in all questions instead of using index. this way its way easier to write base cases, because you can clearly call out whats the answer when length of array is 0
Striver, why can't we return INT_MIN , in the base case. Because if we return 0, it will be added to 1 and the resultant number will be considered for maximum. And even if it is not the maximum, it will be returned. Your explanation is very intuitive.
understood sir i don't even think of dp those days but now i am doing dp questions without any hint or watching videos!!!! Thanks a lot striver bhai!! :)
hey striver this is regarding ur tuf website......one feedback....can you add another checklist to mark important or tough nut questions so that for revision we can se it carefully again....because this subsequence is screewing up my brain :)
![SAFEPLANET - ดาวเคราะห์ [ THE PLANET ]](http://i.ytimg.com/vi/4X1XL3I_k3c/mqdefault.jpg)
Understood and you've completely changed my life. Doesn't matter if I get placed in a good company or not but the quality of this lectures are supreme and I will carry this knowledge for rest of my life.
Keep trying. It will work out. Dream for the day when you are so good that you REJECT your dream company.
@@AdityaKumar-be7hx Requires god level consistency to do that.
You will probably forget the concepts, since these are never used in the industry. What a satire !
🤣🤣@@idris110
brother are you placed
If someone is following Striver's series then this LCS is also a cakewalk..#Striver gives u confidence and you are no longer scared of dp😁
In the future, Mr. Vikramaditya will go down as the G.O.A.T online DSA teacher.
Yes he is GOAT
I am the future
He is already for me.
No a Guy named Srikar From Vizag will go down as the GOAT online DSA in future
@@v7gamerff809as usual, just a dumb guy from ap.
True
Protect this guy at all costs. Thank you sir for all your hard work in making this video.
Everyone should be protected bro
putting your years of hardwork in some videos ,how lucky we are,Thanks a lot striver bhaiya for everything you are doing for us
I used to be scared of Dp when I started coding journey, but when I am actually doing it, it's cake walk. Thankyou striver for sharing your knowledge.
No other video on the topic will offer you a better explanation than this! This is just pure teaching excellence! Subscribed.
understood bhaiya!!! after a very long time i am back to your channel....previously i was doing a race that as soon as you upload the video, i should watch it then n there, before the next video gets uploaded in this dp series, but due to some busy schedule, i lost the race. yeah, but your quality and energy is still the same as your starting videos
You're a great teacher. If possible, please do problems about DP on tree. I struggle with them. Thank you!
46:05 for space optimization we don't require the loop for prev as the values are already zero in it.
Loop is required in C++ to initialize array with 0s. But for Java it is not required as by default array is declared with 0s.
@@dikshamakkar2850 I have a question , vector dp(n + 1, vector(m + 1,0)); this line of code initializes all index to 0 then why did he ran 2 more loops to initialize some row and column to 0 again?
@@dikshamakkar2850 nah loop isnt required
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vectorprev(m+1,0),curr(m+1,0);
for(int i=1;i
you're right but that's write for clarity purpose that how we are generating tabulation from already written memorization solution
@@vizzz8906 he forgot to remove this loop.
I am very grateful to you for uploading this playlist. This is great!!!!!!!!!!!!!!!!!!!!!
Understood.
This was life-changing. Thank you Striver, you taught what paid courses could not for so many years. I wish I had discovered your site earlier; it would have saved so much time and energy.
15:34 "You kow i am hearing you" in the background
So?
Understood!! I don't think any other explanation video can match this one. You are God sent!!
absolutely minds bogling.i am not kidding i wasn't able to solve simple recusion questions few weeks ago now i can solve medium and hard dp questions on my own without watching videos.all i can say thank you striver.
If someone is using java to write the code, in space optimization approach there will be error in a testcase, to resolve that error replace prev = curr with prev = curr.clone(); or else use the code snippet
int [] temp = prev;
prev = (curr);
curr = temp;
Because in java prev = curr will not create a new array but it will point both the references to same address.
Your program would work fine.
US ❤
I should mention I am solving DSA consistently from past 1 year. Encountered this question a lot of times.
But till date this is the best explanation boss❤
bro!!!!!! What an explanation, absolutely brilliant. I am starting to love coding now. Thanks
Its taking while to digest this information for me ,
Just imagine the efforts this guy is adding to make it available for everyone.
for those who don' t want to use shifting of index in tabulation , they can do it in traditional way using below code. we can discuss if you have any doubts.
int longestCommonSubsequence(string text1, string text2) {
int n1= text1.size();
int n2= text2.size();
vector dp(n1, vector(n2, -1));
//filling first coloumn of the matrix
//say we have text1= bcade and text2=a then
//the longest cmmn subsqnce is 0 until index1 reaches 2, once it reaches 2 beyond that lcs =1;
for(int i=0; i
What a brilliant explanation, I come here after watching Aditya Verma's videos on DP but didn't feel the intuition behind the tabulation that he was doing and now I know the thought process all thanks to Striver.
Honestly, everytime i listen to you dude i feel like i can handle anything ! much love from Paris
best explanation I have received ever. U are the best. Im watch this whole playlist to prep for my interviews
you are a god level teacher🙇♂🙇♂🙇♂
never thought dp would be so easy
Giving my best shot for preparing for my placements. Let's see what happens in upcoming months. Great Content
UNDERSTOOD.....Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood, always in awe of you genius and hard working you are:)
bro striver you have taught so well that i didnt even need to watch the video,i solved the problem in all three ways,thaank you very much❤
simple space optimization technique : just 2,3 chanes
instead of using 2 different vectors we can just change dimension of dp to [no of previous rows we wanred + 1][no of colum]
int longestCommonSubsequence(string s1, string s2) {
vectordp(2, vector(s2.size()+1, 0)); // changing dimension as per need
for(int i=1; i
You can't find better explanation than this, Brilliant!!
Again @takeUforwad, just letting you know, again that's stuff you have done, is GOD's own work, thank you for from bottom of my heart, thanks !!!
What an easy explanation, loved it !
I solved with different tabulation approach (without shifting index) as below:
int m=text1.length();
int n=text2.length();
int[][] dp = new int[m][n];
int temp=0;
for(int i=0; i
same
Believe or not Striver
I solved the problem by myself without seeing this video
Note : I gone through all your previous dp videos properly with no skip :)
I am so happy.. Thanks to you.
Understood!!!
Same tabulation method that you taught in previous videos... Same approach without index shifting.
Base case in Memoization :
if(index1 == 0 || index2 == 0) {
return s1.charAt(index1) == s2.charAt(index2) ? 1 : 0;
}
Tabulation :
static int tabulation(int index1, int index2, String s1, String s2) {
int[][] dp = new int[s1.length()][s2.length()];
dp[0][0] = s1.charAt(0) == s2.charAt(0) ? 1 : 0;
for(int i = 1; i
I’m just so thankful to you for this wonderful series, I’m honestly enjoying it dude, surely you’re one of the best!
I even did the problem by myself so easily, i was shocked believing😂
me too😂
Very nice explanation sir, Thank you!
most in depth explanation, thanks
I was able to see that curr= prev; mistake as you were typing it. thanks to you Striver. you are the best
he is the example of beauty with brains
hey man i know you are a very good teacher , but you are also a very good human being.
who agrees that this dp series is one of the best on TH-cam
Not one of the best no. THE BESTTTTT!!!!!
Man the content is gold.
Amazing lecture sir ❤❤❤.
Thanks for all your efforts for us.
understood .....thanku striver .....let's finish this dp on string topic
Without right shifting the Indexes, still we could do it as default initialise with 0 and then start from i=0 and j=0 but adding constraints of out of bounds.
#include
//Tabulation Solution
int lcs(string s, string t)
{
int n1=s.size();
int n2=t.size();
vectordp(n1,vector(n2,0));
for(int i=0;i=0){
dp[i][j]=1+dp[i-1][j-1];
}
else{
dp[i][j]=1;
}
}
else{
int a=0,b=0;
if(i-1>=0){
a=dp[i-1][j];
}
if(j-1>=0){
b=dp[i][j-1];
}
dp[i][j]=max(a,b);
}
}
}
return dp[n1-1][n2-1];
//Write your code here
}
I did the same with java code
If you started new topic like DP on string it is important that you should explain each problem with tabulation method also thoroughly, instead of just writing code, but Great Series.
"UNDERSTOOD BHAIYA!!"
Can also be done using single array if we preserve cur[j-1] in a prv variable
Yeah.. you guys are learning fast 😍
@@takeUforward thanks to your playlist💯
@@tejasghone5118 can u provide the code
@@jaykumargupta7307
int longestCommonSubsequence(string s1, string s2) {
int n = s1.length(), m = s2.length();
vector cur(m+1, 0);
int prev;
for(int ind1=1; ind1
can u give the video link in which he taught this space opt technique
if someone doesn't want shifting they can write base case as below
idea is to make let say dp[0][i1]=1 and also all further i>i1 equal to 1 eg dp[0][i1+1]=1,dp[0][i1+2]=1,....
similarly for second loop also
remember what dp[i][j] represents: ;length of lcs of substring s1[0...i] and s2[0..j]
bool b=false;
for(int i=0;i
understood.wonderful. amazing. hats-off. unmatchable.
Understood. Only one point, if you are doing the tabulation to eliminate the O(m*n) S.C and then including (m+n) extra space for an extra row and column, it seems a bit redundant.
m+n
Understood..! Awesome method "shifting of index" 😁......though without shifting i have solved tabulation, all credits to you only, but shifting of index makes that too easy. Love you ❤
Thank you Striver for such a wonderful explanation. Finally understood it intuitively. 💯💯
striver help this brother out!
how you are staying disicplined?
so far you are single ,right?
how you are avoiding every distractions and focusing on your goal
please make a video on this brother!!
understood thank you Striver
Nice explanation raj bhaiyan or dude, I might call you angel!🥰🥰
Understood very well
In Tabulation we are declaring vector with values zero. So we can skip first two loops.
I deeply understand recursion, memoization, tabulation and space optimization.
Today, I solved my first ever dp problem in a contest just by watching this video...
Codechef Starter 71 Longest Common Subsequence problem
understood,previously I mugged up the tabulation formula for the exam ,but now I know how it came.
UNDERSTOOD...
Thanks striver for the video... :)
Was able to solve this on Leetcode by myself. Thanks Striver !!!
public int longestCommonSubsequence(String s1, String s2) {
int n1 = s1.length(),n2 = s2.length();
int[] prev = new int[n2];
//base cases
if(s1.charAt(0)==s2.charAt(0)) prev[0]=1;
for(int i=1;i
Thanks bro the Playlist is top notch...am getting a lot better...Thanks again
Dhonnobad Brother
You are great
Finally DP on strings Let's Go
Once again thanks for this awesome content
Thanks for great explanation striver
best dp playlist on youtube
Just one word , Beautiful!
Understood ❤
thanks for beautiful explanation
You are a rockstar.. loved it
i myself did it 1array space optimisation ! quite impressive how i learnt that fast 😀😀
can you please share the code of 1 array optimisation , my 1 array code giving me wrong answer on leetcode testcase 23 , i saw a solution where someone uses 2 extra variables to do in 1 array. plz reply
In interviews do we need to show the overlapping subproblems by taking longer examples or we can simply move on with memoization?
take till 5 to 6 steps., if recruiter does want , want he will tell u., to move to next step.
Understood! Awesome explanation as always, thank you very much!!!
Understand it very clearly>>
I was always scared of these LCS and all but not anymore thanks to striver
god!!! of teaching dsa
understood
IN TABULATION WE CAN STORE 0 INTIALLY AND skip the base case loops which is used to store 0 in 0th row and column and same for space optimization
Understood sir very well!!
Continue from 23:30
Understood,you are doing the great job , very thankful to you
did it in 1st attempt without seeing the video, shifting index to right was new to me
pro tip -> use right shift method in all questions instead of using index. this way its way easier to write base cases, because you can clearly call out whats the answer when length of array is 0
I didn't get it could you please explain a lil bit.
GOAT for a reason❤❤
Striver what do u eat, how can be someone explain in such an excellenct manner❤
awesome, understood..was pretty easy due to what you've alrready taught
Understood, Thank you so so much.
Striver, why can't we return INT_MIN , in the base case. Because if we return 0, it will be added to 1 and the resultant number will be considered for maximum. And even if it is not the maximum, it will be returned. Your explanation is very intuitive.
understood
sir i don't even think of dp those days but now i am doing dp questions without any hint or watching videos!!!!
Thanks a lot striver bhai!! :)
This man is saviour. Thanks bhaiya ❤️
US Striver , Getting into Google i can image ur DSA level 🔥
hey striver this is regarding ur tuf website......one feedback....can you add another checklist to mark important or tough nut questions so that for revision we can se it carefully again....because this subsequence is screewing up my brain :)
one of the best dp series
You are amazing ❤️.
Thanks a lot for this valuable content 🙌🙇🙇
when the character was not matching why are we not considering the possiblity of f(index1-1,index2-1). Thanks for the help
Thank You Very much Striver !
Understood 🙂🙂💚