Longest Common Subsequence | Recursion | Memo | Optimal | Leetcode 1143

This is the 10th Video of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will try to solve a very good and famous DP problem - Longest Common Subsequence (Leetcode 1143)

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Longest Common Subsequence (Leetcode 1143)
Company Tags : Microsoft, Amazon, FactSet, Hike, Citrix, MakeMyTrip, Paytm, VMWare

Approach-1 Summary : The approach uses a recursive approach with memoization to avoid redundant computations. The memoization is achieved by maintaining a 2D array t of size 1001x1001, initialized with -1. The function LCS recursively computes the length of the LCS by comparing characters of the two strings. If a subproblem's result is already memoized, it is returned directly; otherwise, the LCS is calculated, and the result is stored in the memoization table. The final result is obtained by calling the LCS function with the lengths of the input strings and initializing the memoization table before starting the computation.
Approach-2 Summary : The approach uses dynamic programming with a 2D vector t to store intermediate results. The code iterates through all possible pairs of indices, filling the table based on the recurrence relation for LCS. The final result is the length of the LCS for the entire input strings, stored in t[m][n], where m and n are the lengths of text1 and text2, respectively.
Approach-3 Summary : It utilizes a 2-row 2D vector (t) to store intermediate results, reducing space complexity. The code iterates through the strings, updating the table based on the LCS recurrence relation. The final result is stored in t[m % 2][n], where m and n are the lengths of the input strings. This optimization maintains the same functionality as the original code but with reduced memory usage.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear

[adityajha]

Your way of explaining things out is really awesome brother. Keep it up and please keep uploading videos, you will surely be successful !

[riyanshbiswas]

Hi Mik, I had done this question earlier through some other explanation by some other Youtuber. Today I saw this question again and totally forgot how to solve it. I searched for your video and trust me when I say this, i will never forget the solution now because now i UNDERSTAND how it works intead of memorizing it.

You make it incredibly easy to 'understand' the underlying algorithm. Keep posting videos, you are an extremely good teacher.
Teaching is an art, and you are Picasso!

[espio]

Your teaching is working so well, your method of solving is sticking with me. I didn't even understand recursion well a week ago and today I watched your explaination and coded the solution myself and I'm so proud of it.
Thank God that I found your channel and such an amazing Teacher <3

[AbhijeetMuneshwar]

The best part that I love about your video is that you tell the reason for doing every step. This helps understand the intuition and logic easily.

[statusroom]

After watching starting of 5 min i solved it by myself.
Thanks for the wonderful explanation.

[realAB]

Really Great explaination ! I found your channel from gfg comment section

[molyoxide]

Question was HARD but MIK made it EASY.🎇

[FanIQQuiz]

Aag laga diya bhai. Awesome explanation. you make things so easy

[singhshek]

Thank you bhaiya for such nice explanation and very easy to understand . I saw many youtube channel but your way of explanation is so nice that it tells all what is happening in the code 😊

[jagadeeshp]

Notes:
In every recursion problem we face we only have one index but here we have two strings we need to maintain 2 indexes for each of them
Now the main funda is which one to move how to move
If i say i move s1 index everytime then think of this case
s1 : abcd
s2 : fabcd
if i move s1 ahead then my new search space becomes
s1:bcd s2: fabcd
s1:cd s2: fabcd
s1:d s2: fabcd
s1:"" s2: fabcd
we got zero at the end but if you see carefully the answer for this "abcd" and fabcd" is "abcd" which is 4 but we got 0

conclusion i cannot only move s1 ahead✅

If i say move s2 index everytime then think of this case
s1:"fabcd"
s2:"abcd"
if i move s2 ahead then my new search space becomes
s1:"fabcd" s2:"bcd"
s1:"fabcd" s2:"cd"
s1:"fabcd" s2:"d"
s1:"fabcd" s2:""

we got zero at the end but if you see carefully the answer for this "fabcd" and abcd" is "abcd" which is 4 but we got 0

conclusion i cannot only move s2 ahead✅


So the only choice i have is i need to check for both of them once i assume index1+1 and in the other case i assume index2+1 where index1 corresponds to s1 and index2 to s2

Observations/Story
if s1[index1]==s2[index2] ----> we can add one to our count
else: we need to explore both the choices and get the best answer out of them or maximum as per question
We see some states are same we can memoize it as well

Recursion Approach: TLE⏲
class Solution:
def solve(self, index1, index2, text1, text2):
if index1>=len(text1) or index2>=len(text2):
return 0
if text1[index1]==text2[index2]:
return 1+self.solve(index1+1, index2+1, text1, text2)
else:
return max(self.solve(index1+1, index2, text1, text2), self.solve(index1, index2+1, text1, text2))

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
return self.solve(0, 0, text1, text2)

Recusrion + Memoize :✅
def solve(self, index1, index2, text1, text2, dp):
if index1>=len(text1) or index2>=len(text2):
return 0
if dp[index2][index1]!=-1:
return dp[index2][index1]
if text1[index1]==text2[index2]:
return 1+self.solve(index1+1, index2+1, text1, text2, dp)
else:
t=max(self.solve(index1+1, index2, text1, text2, dp), self.solve(index1, index2+1, text1, text2, dp))
dp[index2][index1]=t
return t

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp=[[-1 for i in range(len(text1))]for i in range(len(text2))]
return self.solve(0, 0, text1, text2, dp)

Done Thanks Mik i used to cramp LCS everytime Before i got to know your channel
But now i'm able to do 🙇‍♂❤
#storyToCode

[akshaychavan]

PURE GOLD!
I wish I had a teacher like you for my DS Algo class :(

[souravjoshi]

This is the best explanation I have ever seen for this problem.

[Sawlf]

The way you explain the recursion tree that alone becomes enough to solve the problems <3.

[umangbehl]

i always appreciate the intuition you make us understand

[wearevacationuncoverers]

You explanations are next level really

[parthbhatti]

now i'm able to build tree by myself but it just matter of practice and i'm able to code it because i learn to make tree by my self and as usual able to findout the DP as well 🚀

[Anushka_]

bhai if possible web development bhi sikha doo !!
dsa tho OP

[adwaitmhatre]

You are truly amazing brother!!…just one doubt: do we have to give the bottom up approach in interview?…will giving only recursion+memo suffice?

[ishwarkokkili]

bas itni simple chiz ka itna hawva bana diye the log ? - *people after MIK drops a vid.

[Ajeetkumar-uohf]

I watch other videos on youtube but those videos explanation is not even close to your explanation.❤