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

Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3pvkqUd
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the LCS Dp, this is the first problem on the pattern Strings on DP.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward

[@sujalgupta6100]

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

[@anweshabanerjee6241]

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😁

[@manthenanagendra1077]

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

[@art4eigen93]

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

[@wahtNIGGA]

Yes he is GOAT I am the future

[@abhishekkarn8918]

He is already for me.

[@pratyakshsinha6292]

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.

[@AdityaKumar-be7hx]

Keep trying. It will work out. Dream for the day when you are so good that you REJECT your dream company.

[@iamnoob7593]

@@AdityaKumar-be7hx Requires god level consistency to do that.

[@idris110]

You will probably forget the concepts, since these are never used in the industry. What a satire !

[@bharatravihal9646]

🤣🤣@@idris110

[@spoidy2025]

brother are you placed

[@arunkumarsahoo1344]

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

[@jeet-smokey]

So?

[@arjundevmishra7207]

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

[@mayanksingh7501]

Everyone should be protected bro

[@Amitchoudhary-ij4we]

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

[@avimandavia6154]

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

[@duyhuynh1234]

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

[@ramanahlawat398]

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

[@kanikajain5627]

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.

[@kartiksuman9814]

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

[@yashsinghal3404]

What an easy explanation, loved it !

[@mahammedhashish9170]

You can't find better explanation than this, Brilliant!!

[@mjmusic65]

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.

[@akashyadagouda896]

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

[@stith_pragya]

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

[@nottheradbrad184]

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❤

[@ankita716]

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

[@BG-lj6fw]

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

[@donno2423]

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.

[@cinime]

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

[@pratapsingh9638]

Understood,you are doing the great job , very thankful to you

[@virgarg1012]

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

[@VishalYadav-gk1kg]

Very nice explanation sir, Thank you!

[@ranasauravsingh]

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

[@deepurana6010]

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

[@Nikhil-ov6sm]

awesome, understood..was pretty easy due to what you've alrready taught

[@arnabroy2995]

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❤

[@shivamsinghnegi1192]

Thanks bro the Playlist is top notch...am getting a lot better...Thanks again

[@sypher4735]

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😂

[@ishitasrivastava8417]

me too😂

[@vinaylj]

I was able to see that curr= prev; mistake as you were typing it. thanks to you Striver. you are the best

[@pj-nz6nm]

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

[@sameersahu4569]

Loved the Explanation!!Understood

[@ChutHunter]

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

[@dashsights4258]

Just one word , Beautiful!

[@ritikshandilya7075]

Thanks for great explanation striver

[@DevashishJose]

Understood, Thank you so so much.

[@ahsanulanam-4632]

Dhonnobad Brother You are great

[@m4n0jkum4r]

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

[@gyanunlimited740]

Man the content is gold.

[@alokbhowmik3547]

what an explanation thanks for your time and such video

[@sarveshamrute4982]

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

[@saddy4420]

same

[@rohan8758]

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

[@himanshuagrawal8012]

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

[@SethuIyer95]

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

[@daniel.w8112]

Thank You Very much Striver !

[@amartyadas5-yriddmechanica597]

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.

[@takeUforward]

m+n

[@rishabhgupta9846]

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

[@varunsharma1889]

Very good explanation. Understood. Thanks.

[@girishbhargava6367]

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.

[@coding8000]

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

[@ganeshkamath89]

Thanks Striver. Understood LCS.

[@oqant0424]

seriously you are a legit! understood ,thanks🙌

[@thiyaneswarana3656]

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

[@sanyazaveri4511]

Awesome lecture. Understood!

[@avikdey01]

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

[@coding8000]

take till 5 to 6 steps., if recruiter does want , want he will tell u., to move to next step.

[@kareni7572]

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

[@jaideeppyne1880]

very well explained step by step

[@tibebuwassie6017]

hey great video but isn't the auxiliary stack space supposed to be max(s.size(), t.size())?

[@varunbansal1136]

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.

[@jskr456]

very good explanation

[@HarshSharma-ff3ox]

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

[@user-oi6eb7ru2s]

Thanks a lot striver

[@CodeMode9313]

awesome paaji

[@vishious14]

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

[@honeykumar5700]

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

[@justarandomguy6106]

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

[@harshitatripathi6440]

best dp playlist on youtube

[@yashchawla3729]

Understood, sir. Thank you very much.

[@rahulsaha332]

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

[@Parmindersingh-of6oo]

We don't need to add base case while bottom-up in case of index shifting. If we just replace "-1" with "0" while initializing dp vector. Isn't it?

[@user-ke7fs7ds6h]

GOAT for a reason❤❤

[@jarvis3551]

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

[@abdallaalhag4425]

Understood boss man!

[@AmanKumar-qz4jz]

god!!! of teaching dsa understood

[@harisai3580]

Understood Sir!

[@AbdulKadir-bh3el]

understood bruh, plz make video on sliding window technique too.

[@tejasghone5118]

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

[@takeUforward]

Yeah.. you guys are learning fast 😍

[@tejasghone5118]

@@takeUforward thanks to your playlist💯

[@jaykumargupta7307]

@@tejasghone5118 can u provide the code

[@himanshuguleria9474]

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

[@ishwarshelke128]

can u give the video link in which he taught this space opt technique

[@priyanshuchouhan9845]

one of the best dp series

[@santoshb7776]

Understood sir ! 🙏🙏

[@rpriyanka28]

he is the example of beauty with brains

[@meetharsoda5152]

Finally DP on strings Let's Go

[@abhinavgoli868]

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

[@vedxnt10]

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

[@iamnoob7593]

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

[@prabhakaran5542]

Understood ❤

[@coderrr3353]

This man is saviour. Thanks bhaiya ❤️

[@raj_kundalia]

thank you so much!

[@himanshugoyal7941]

Can anyone please explain why (index1 == 0 || index2 == 0) has not been considered as base case here as we did in DP of arrays? In DP of Arrays, I was trying to use (index < 0) as the base case, but when I saw Striver's video, I changed my approach to his, where he was considering (index == 0 ) as the base case. But now, in this, he is using the other way around. Can someone please explain why?

[@sanyattaneja8551]

You can use index1 == 0 || index2 == 0 but then it will have 2 cases 1) if(index1 == 0 && index2 == 0) return s1[index1] == s2[index2] ; 2) if(index1 == 0 || index2 == 0) \\ using loop find the single character(having index == 0) in other string if present return 1 else return 0 therefore it is difficult to find and index < 0 base case is much easier so it's better to write that

[@jashhinger442]

Love the concept ✨

[@lambar0]

Clear and Simple

[@md.rashedulislam5141]

Is it possible to represent every dp problem by recursion tree?

[@lakshmanpadigala1605]

Great explanation!

[@SurajPrasad-bf9qn]

you are too awesome bro

[@UECAshutoshKumar]

Thank You Understood!!!

[@ScienceSeekho]

Thanks learned new thing index shifting

[@thanhbinhnguyen5943]

nice explaination !

[@jitendrasinghsola]

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

[@hemanthkumar516]

in tabulation method to avoid getting negative values this condition can be used if(i1==0 || i2==0){ if(s1.charAt(i1)==s2.charAt(i2)){ dp[i1][i2]=1;} else if(i1==0 && i2!=0){ dp[i1][i2]=dp[i1][i2-1];} else if(i1!=0 && i2==0){ dp[i1][i2]=dp[i1-1][i2]; } }