Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing Subproblems

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: You are given 2 strings. Return the length of the longest subsequence that the 2 strings share.

Complexities

Time: O( nm )

We can upper bound time by the number of subproblems that we are going to solve.

Space: O( nm )

We upper bound space by the number of subproblems we will story answers to. Whether we do (n + 1)(m + 1) or (n)(m) doesn't matter asymptotically.

++++++++++++++++++++++++++++++++++++++++++++++++++

[BackToBackSWE]

Table of Contents:

The Problem Introduction 0:00 - 0:25
What Is A Subsequence 0:25 - 1:00
Going Through Examples 1:00 - 2:37
Walking Through A Recursion Tree 2:37 - 12:00
Recursion Tree Finished: Our Answer 12:00 - 13:18
Dynamic Programming Table Walkthrough 13:18 - 13:43
What Are The Subproblems? 13:43 - 14:56
Defining Our Base Cases 14:56 - 16:24
Working On The Inner Table 16:24 - 22:49
DP Table Finished: Our Answer 22:49 - 23:27
This Is Not Intuitive At All 23:27 - 24:11
Time & Space Complexity 24:11 - 24:49
Subscribe Por Favor 24:49 - 25:11

The code for this problem is in the description. Fully commented for teaching purposes.

[shubhamasati]

somebody give this guy an oscar ...plz

[heyitsnikhil]

"okay. this is not intuitive at all. I'm going to be outright and honest."
-thanks for saying this. sounds relieving. 😂

[adriantran]

The dp table explanation is the most beautiful thing I've ever seen

[ssparks]

It was almost like you were speaking directly to me when you said "Stay with me! Stay with me! I know it is confusing." Thank you so much for this thorough explaination!

[sandarabian]

I was so stumped when the problem was introduced, then at 4:22 it was like a bucket of genius water was dumped on my head. Genius!!

[TeeheeTummytums]

This is absolutely unbelievable that I just now found your channel. Thank you so much for all your hard work. Keep up the great work!!!

[memoriesadrift]

This is honestly the best video I have seen on dynamic programming on YouTube. Mad respect to you for you for your down-to-earth, simple to understand explanations.

[ravishekranjan]

This is the best explanation of LCS along DP available on internet.

[ful]

This video was so good I almost cried... (tears of joy). Amazing work!

[Themerp]

Thank you so much. I have finally been able to understand Dynamic Programming Tabulation method. Most people when trying to explain it focus only on the table and don't explain how the code relates to the table properly. Now I understand it. You really have a gift for teaching, keep doing what you are doing. I will make sure to support this channel when I finally get a job

[rajeshseptember]

I was almost about to give up on "Dynamic Programming" until I saw this video. Best video on the internet for DP !
Hats off man !! Commendable job

[doruwyl]

What sets you apart from other coding solving videos is the depth you go into and the effort you put in order that your audience would really understand how to solve the problem.
Well done!

[ShortGiant]

Thank you! You're like stackoverflow for leetcode. The place I look for help when I'm either stumped with a problem, or I've solved it but want the concept firmly set into my head.

[LoneWolf.]

Your teaching style is best. Why am I saying this?
When you were going through the explanation the moment I was falling in confusion you were just there to tell "wait, this might be confusing but I will explain". This gave me the confidence and continued. DP was a nightmare to me. I just got what I wanted. No words to thank you enough. I am from Bangladesh, and I want to say my gratitude, man! Amazingly great explanation.

[blackkiritok]

Ok. How easily you explained this is beyond words. Many can code stuff but very VERY rare can explain the way you did.
This problem haunted me for around 6 months and after this video I solved it without a sweat
I can officially say you have GODLY skills. Thank you so much!

I am going to spread this video (or your channel in general) to as many of my friends as possible. Please keep up the good work.

[tanvia]

I FINALLY understand. Thank you so much.

[aakashbansal]

Man, Can DP be explained any better than this? Hats off!!!! Thanks for all this stuff. Really made DP a cake walk for all us viewers...

[ayushanand]

The best ever video on this problem! While other people scream out that their playlist is the best, this man literally nails everything down!

[bhaskarroy]

I have gone through numerous videos but none of them could explain this problem in a level of depth like you did. Thanks a ton!