Longest Common Subsequence - Recursive and Iterative DP (LeetCode Day 26)

[@Errichto]

Educative giveaway winners were contacted via email on May 2. You can also see a censored list of winners at the beginning of this stream kzbin.info/www/bejne/l3KnlHWur759b5Y

[@shubhamtomar95]

I like how talented, confident and yet humble errichto is! :)

[@kaueluisoliveiradasilva9403]

Best channel about coding! Please keep posting.

[@bethsuni4011]

6:24 this is King Crimson's ability. Errichto confirmed stand user.

[@reiter2148]

it's also exactly 10 seconds!

[@williamwambua7710]

Yeeeeehhhh Now Errichto has sponsors!!! Progress

[@phillip4833]

I hope you keep growing in your youtube career world and in your competitive coding career. Awesome you share your experience and problem solving skills with us.

[@arkalykakash9475]

Great explanation. Thank you Errichto!

[@nowarm]

thank you so much Errichto for sharing your knowledge. I really enjoy thinking and learning with your explanation. It makes so much sense.

[@nisharege857]

So what is better iterative or recursive? Best explanation!!!

[@ClaudioBrogliato]

Damn, I started with the recursive approach but when I hit the time constraint I wasn't sure caching would be enough to pass and so I changed my mind and went iterative.

[@cobrandrewg9995]

Finally a sponsor😂

[@hamzaxvz]

please keep posting videos like this, all the best..

[@parthokunda]

Awesome video. Really loved your explanation.

[@flamendless]

Awesome! Please explain the iterative solution with drawings.

[@raahelbaig8347]

I looked up the algorithm on Back to Back SWE. I couldn't solve it on my own. This question was my first cheat in the challenge.

[@BedoEbied]

I gave up and didn't cheat I left it until I came back with some DP knowledge

[@amanrubey]

My wish is to watch Errichto solve questions daily

[@ankitacharya7520]

So humble.

[@rajsahu1386]

please discuss the problem of minimum string coefficient of hackerrank hack the interview 2

[@Expanses02]

My recursive solution got TLE and iterative solution got accepted. Is there a significant difference in there execution time , since the complexity is same too ?

[@charan775]

generally, iteration is faster recursion due to recursive call stack frames

[@vishalvatsalya1439]

Can you please do the Hack the Interview 2 problem explaination for the last questions? 😅

[@amanrubey]

Insanely fast typing speed!!

[@lovvyparhar393]

Instead of writing find and all we can use map.count(key) to know if the element is present in the map or not. I find it very useful.

[@andreacodutti1313]

But what if you want to modify the key? You would have to spend more time searching it again. (Or maybe the compiler can optimize and it would be the same thing)

[@lovvyparhar393]

@@andreacodutti1313It is just a matter of convenience. Otherwise if you are in a time sensitive situation, and it is being called multiple times then you can consider the other option.

[@audiogear4412]

Keep posting more!

[@ryukshinigami5216]

General doubt : if I have a vector pair of int and string vector if I want to sort using direct stl sort function... It will sort using first value.... If first value is same for some two elements then it will sort according to lexicographical order of string but i want to sort according to first and then see if two elements of first are same then I want the first value which came first when I had push_backed and maintain the relative order what should I do?

[@amandixit3555]

can you please a playlist of good dp question explaing how to figure out reccursive function in dp questions

[@emmanuellmiqueletti7029]

I'm a Java programmer and love how C++ is flexible. this code wouldn't compile in java because he's returning in the first line of the method. C++ accepts but Java doesnt.

[@CristhianR51]

Hi Errichto, any particular reason to why you used a map instead of an int matrix when going for the recursive solution?

[@AnthonyMata]

These vids are so handy

[@TwoTeaTee]

Nice video! 👌🏼

[@shubhamtomar95]

VIDEO/SERIES REQUEST : solutions and explanations for problems in CodeJam Archives.

[@mohammedshoaib1635]

Petition for Errichto to pop his fingers for intro 🙌

[@camper8650]

Leetcode is very unpredictable

[@vinaykataria5998]

Standard dp problem 😊❤

[@techesigncorp869]

hi Your videos are great .Thanks for making them .I have question actually can anyone do competitive programming as js developer .

[@johnnashcz]

thinking of DP while programming can be distracting :D

[@edwardsnowden9573]

I started programming. But I can't focus on one curriculum. Different materials pop up unexpectedly. Show me a curriculum that I can follow

[@charan775]

maybe follow codechef dsa syllabus. very good resource

[@jin8128]

hi EDWARD SNOWDEN how is it in Russia?

[@edwardsnowden9573]

@@jin8128 it is pretty good 😂

[@emmanuellmiqueletti7029]

any problem the interviewer give this guy. the interview probably will learn something hahaha

[@utsavsingh899]

He doesn't pop his fingers no more🙁

[@himanshugupta7647]

@Errichto can we become good in 1 year

[@sauravchirania5725]

Nice videos! Why do you have a timer though? Having a timer when practising problems is understandable, but why have a timer when explaining the problem / solution to others?

[@ZulfiqarTariqBurmi]

erric took some 19 minutes to solve it and he is one of the best competitive programmer so how can a company expect college graduates to solve it in 45 mins?

[@SajidAli-fn9tp]

He could have solved it in a couple of minutes but he was explaining the intuition and thought process behind both the recursive and iterative version along with the coding. He has many years of competitive programming experience.

[@jiaxinsun9444]

I need two other of me to catch your thinking.

[@audiogear4412]

Plus blue yeti just sucks. Your voice is good.

[@miteshkumar5557]

There is a faster NlogN approach that people used. Why didnt you use that?

[@waatup]

Let m and n denote the lengths of the two strings. Changing the problem into longest increasing subsequence does give you O(NlogN) but notice the N is not the length of the strings, but rather the dot product of the occurance count vector; for example, if a occurs 5 times in text1, and 3 times in text2, then a would contribute 5*3 = 15 to N. On average, you should still expect N to be O(mn), just with a much smaller constant because N is on average mn/(26^2). In practice that logN is never gonna outweigh 26^2, so converting to LIS is indeed advantageous for most cases. However, in the worst cases where the two strings are just two characters randomly alternating, like aabaababaabaa and ababaabaababaa, it ends up having a worse time complexity by a factor of roughly log(mn), while the space complexity is comparable. This can be mitigated somewhat with 1 additional comparison before doing the binary search, not sure how much it helps but probably by quite a bit.

[@rentib9136]

I hate dp and it seems leet code is planning on giving a lot of problems dp-related... Literally everything would be better, even geometry (I know its your favorite Errichto) or segment trees on graphs. Can you make a vide on changing LCS to LIS ?

[@chaitanyakumar9455]

how to do it in O(N*log(N)) time complexity ?

[@waatup]

changing the problem into longest increasing subsequence does give you O(NlogN) but notice the N is not the length of the strings, but rather the dot product of the occurance count vector; for example, if a occurs 5 times in text1, and 3 times in text2, then a would contribute 5*3 = 15 to N. On average, you should still expect N to be O(mn), just with a much smaller constant because N is on average mn/(26^2). In practice that logN is never gonna outweigh 26^2, so converting to LIS is indeed advantageous for most cases, and the worst cases shouldn't be worse than the DP solution. The space complexity has a similar story.

[@vivekksahu271]

@Errichto, Make your my_LCS() fn (in non-DP version) as private and see what happens. Your code wouldn't even be accepted.

[@tonymok535]

I got TLE for recursive approach in python haha but iterative approach was accepted

[@philtoa334]

Nice

[@BedoEbied]

Sadly I don't know DP :'(

[@user-mr-m12312]

So learn it :) Errichto has free playlist about dp on this channel: kzbin.info/aero/PLl0KD3g-oDOGJUdmhFk19LaPgrfmAGQfo

[@10xGarden]

I didn't know as well a month back, but its really blissful once you atleast learn it! Solve a few a problems from leetcode after Errichto's playlist

[@BedoEbied]

gonna hit it up!

[@whitesalmon0925]

YES!!!

[@annawilson3824]

Dude for real, is this a home-debug video or for the whole youtube to see it? Hm ...

[@SaltyWound]

I will report you for r@pe- -of my brain

[@rohandalvi6476]

I understood Nothing

[@audiogear4412]

The coding style is ugly as hell. Why not use lambdas for recursive functions instead of private member variables?

[@c_tanki207]

did u think of the solution of last night in sleep(subconscious ) ?? if yes then like hehe

[@secretmystery8305]

Nice