Dp 25. Longest Common Subsequence | Top Down | Bottom-Up | Space Optimised | DP on Strings 

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.

In the future, Mr. Vikramaditya will go down as the G.O.A.T online DSA teacher.

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😁

putting your years of hardwork in some videos ,how lucky we are,Thanks a lot striver bhaiya for everything you are doing for us

Protect this guy at all costs. Thank you sir for all your hard work in making this video.

46:05 for space optimization we don't require the loop for prev as the values are already zero in it.

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.

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

15:34 "You kow i am hearing you" in the background

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.

You're a great teacher. If possible, please do problems about DP on tree. I struggle with them. Thank you!

No other video on the topic will offer you a better explanation than this! This is just pure teaching excellence! Subscribed.

I am very grateful to you for uploading this playlist. This is great!!!!!!!!!!!!!!!!!!!!! Understood.

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

Its taking while to digest this information for me , Just imagine the efforts this guy is adding to make it available for everyone.

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!!

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.

bro!!!!!! What an explanation, absolutely brilliant. I am starting to love coding now. Thanks

who agrees that this dp series is one of the best on RU-vid

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

understood, always in awe of you genius and hard working you are:)

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❤

Giving my best shot for preparing for my placements. Let's see what happens in upcoming months. Great Content

Very nice explanation sir, Thank you!

What an easy explanation, loved it !

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.

Can also be done using single array if we preserve cur[j-1] in a prv variable

Nice explanation raj bhaiyan or dude, I might call you angel!🥰🥰

understood .....thanku striver .....let's finish this dp on string topic

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.

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.

Man the content is gold.

thanks for beautiful explanation

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!!

UNDERSTOOD.....Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

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 was able to see that curr= prev; mistake as you were typing it. thanks to you Striver. you are the best

when the character was not matching why are we not considering the possiblity of f(index1-1,index2-1). Thanks for the help

Striver what do u eat, how can be someone explain in such an excellenct manner❤

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.

he is the example of beauty with brains

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 !!!

In Tabulation we are declaring vector with values zero. So we can skip first two loops.

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❤

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😂

almost all of the questions in this playlist can be space optimized to not just O(2m) but O(m) if you apply some logic and visualize how the table is being filled.

In interviews do we need to show the overlapping subproblems by taking longer examples or we can simply move on with memoization?

Thank you so much bhaiya, I always heard of this question as one of the most difficult ones. But by following your DP series, I did it on my own. You can easily sell this quality content for ₹ 50k but you're giving it for free. BEST TEACHER EVER ♥♥♥♥

Today, I solved my first ever dp problem in a contest just by watching this video... Codechef Starter 71 Longest Common Subsequence problem

"UNDERSTOOD BHAIYA!!"

Understood sir very well!!

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 }

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 ❤

Memoization solution will give TLE on leetcode, simply pass the strings by reference !!

Does interviewers expect us to know the tabulation directly? because I can solve tabulation only after analysing recursion

Understood ❤

I deeply understand recursion, memoization, tabulation and space optimization.

Finally DP on strings Let's Go

Why can't we put the base case at index 0? Especially for LCS - DP on strings related questions?

hey man i know you are a very good teacher , but you are also a very good human being.

I was always scared of these LCS and all but not anymore thanks to striver

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 :)

Thank you Striver for such a wonderful explanation. Finally understood it intuitively. 💯💯

Life Lesson: If Raj tells you to go revise a video, then go revise that video. It's really hard not to understand something once you watch everything in the order he presents.

Understood 🙂🙂💚

Me: getting distracted while watcing the video. Striver: 1:01 dekh ** 😂

understood,previously I mugged up the tabulation formula for the exam ,but now I know how it came.

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

Understood !!

understood.wonderful. amazing. hats-off. unmatchable.

Don't know whether you will watch it or not? But, again @takeUforwad (striver bhaiya), 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!!!

UNDERSTOOD... Thanks striver for the video... :)

did it in 1st attempt without seeing the video, shifting index to right was new to me

Continue from 23:30

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

best dp playlist on youtube

Can we do using single array if we denote prev[j-1] in a variable, keep updating it after every iteration of inner loop ?

Thank You Understood!!!

UNDERSTOOD!

Decode ways is a new kind of pattern on dp on strings i think and that can be covered

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 Striver✨

without shifting tabulation method: vector dp(n1, vector(n2)); if(s[0] == t[0]) dp[0][0] = 1; else dp[0][0] = 0; for(int i = 1; i < n1; i++){ if(s[i] == t[0]){ dp[i][0] =1+ dp[i-1][0]; } else dp[i][0] = dp[i-1][0]; } for(int i = 1; i < n2; i++){ if(s[0] == t[i]){ dp[0][i] = 1+dp[0][i-1]; } else dp[0][i] = dp[0][i-1]; } for(int index1 = 1; index1 < n1; index1++){ for(int index2 = 1; index2 < n2; index2++){ if(s[index1] == t[index2]) dp[index1][index2] = 1+dp[index1-1][index2-1]; else dp[index1][index2] = max(dp[index1][index2-1], dp[index1-1][index2]); } } return dp[n1-1][n2-1];

Thanks for great explanation striver

i myself did it 1array space optimisation ! quite impressive how i learnt that fast 😀😀

Quality content

Undersoood!!

Understood! Awesome explanation as always, thank you very much!!!

god!!! of teaching dsa understood

Just one word , Beautiful!

This man is saviour. Thanks bhaiya ❤️

US Striver , Getting into Google i can image ur DSA level 🔥

you are too awesome bro

Bhaiya ,why cant we solve this question like if we have got two strings then we are eliminating the characters from both strings that are uncommon and dont have frequency 1 (checking that in common characters)..ultimately we will get two resultant strings and if they are equal that is longest subsequence and if not there is no longest common subsequence present ..pls clear my doubt

You are amazing ❤️. Thanks a lot for this valuable content 🙌🙇🙇

Understood❤❤🔥🔥

Understood, Thank you so so much.

Understood...

You always have very good solutions, but your writing is hard for us to clearly get all information, I think we should write upper case for all letters, then it will be helpful for all. Thank you