I don't understand why all these algorithm videos never explain how to get the solution. It's always something random like "max of top and left cell" without ever explaining what those values are. It's like the people making these videos do not even understand themselves.
I totally agree. Having read some more, what I understand is this: The matrix (or table) called LCS[][] created here to fill in the values works like this - row is the length of sequence L1 +1 and column is the length of sequence L2 +1. Now if the value at i-1 (subtracting 1 because the matrix is 1 row and 1 column extra than the original lengths of the sequence) of L1 matches with value of j-1 at L2, it means we have a common subsequence (of length 1). Now if there is any sequence common prior to this character, then that would be at i-1 and j-1, i.e., at length less than the current of L1 and L2 (pre computed in LCS[][]). Hence the solution- LCS[i][j] = LCS[i-1][j-1] + 1. If the character does not match, then either L1 has more characters (uptil i) matching L2 (uptil j-1) or vice versa. We choose whatever is the maximum of two. Let me know if the explanation is not at its best.
Just look at the recurrence relation, you'll understand why. EDIT: Refer to some other source, he doesn't explain what the subproblems are and only how to get to the solution.
I think you know the answer ... practice. I am also unable to understand but I think how dynamic programming should be approached is you will have to go through what we are trying to avoid here. In this case, repeated computation of same things while using recursion. Now we need to overcome this overhead by computing only once for each. We can keep track of how much match has happened before current iteration using a lookup table and proceed using those previous calculations. The best way to store the data of matches two strings is a matrix(2d array).
At 6:42 you can use that G. You say "1 came from the left cell" but it didn't. It is 1 because G matches G, and the diagonal was 0. You skip that G for no reason.
Hello Can u please explain why u picked max(leftcell,upcell) when characters dont match Why we have to increment value of diagonal by 1 when characters match.
did u just read it out aloud from wikipedia but with ur own example. Please explain the approach, so that we can understand how to think of similar problems.
Tanmay Misra This is a specific problem and not a general idea. If you're looking for the general concept the videos at the beginning of the playlist will help you out in understanding the approach.
Please do not forget to mention the time and space complexity of the algorithms that you teach, since it is just as important. Nice explanation by the way :)
you explain the procedure but did not explain how you came up with that procedure.. please explain that also so that we can think the algorithm that solve particular problem...
The table should be drawn in reverse i.e "AGGTAB" in row wise & "GXTXAYB" in column wise, after that if we wanna print the output by printing the matrix that would be the actual table. Thank you
If two sub seqeucnes are of same length then they get concatenated and that is the resulting answer or longest common sub sequence. clear ? s1 = abc pqr abc s2 = abc xyz abc LCS = longest common subsequence is = abcabc.
There can be more lcs's our moto is to find the length and using the table we can find the different lcs also at the same time Suppose thre are two longest common sub sequences like for example String 1: abcde String b: acbde here longest commom subsequence is of length 4 i.e abde and acde
@Kanika, The video that you posted is same as DSA - Tabulation from GFG, why repeat? Expectation from this video was to print the LCS or return a List , I don't see either mentioned in this video.
The video is great! I read a lot of articles do not see how to find out the largest common sub-sequence, but I saw your video, got it...thank you...thank you...thank you
Some videos are really good by i am seriously struggling with the ones by Kanika Gautam, she says a lot of stuff incorrectly, please get them made again by other faculty.
*For everyone asking why the matrix is built this way* : When you are using dynamic programming you need to understand the recursive algorithm you would like to optimize. I'll explain the non-genius solution where you go letter by letter from the start of each string. The DP answer will be built bottom-up which would make the table fill from the end of the string as the vid suggests. In this case (x is L1, y = L2): LCS = { 1 + LCS(i+1, j+1) ; IF x[i]==y[j] max(LCS(i+1, j), LCS(i, j+1)) ; ELSE } This is the top-down approach. Now if you would like to convert the recursive solution to a matrix you need to take a bottom-up approach. And so the algorithm will look as follows: LCS = [N][M] // N = len(x), M = len(y) if x[i]==y[j]: LCS[i][j] = 1 + LCS[i-1][j-1] else: LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) Note that the matrix has to have a initialization row and column where all values are 0 in order to have an answer for i-1 and j-1 in the first run. So if you are coding you should also use the case: if (x[i] == 0 || y[j] == 0) -> LCS[i][j] = 0 You can easily see the correlation between the recursive and the DP solutions. Just keep practicing, it is a skill worth working for and not black magic (as some may feel after watching this video).
Why do we have to get the max of L[i-1][j] and L[i][j-1] if no commonality is found? Is it because of the 0's in the first row and column? Because for other cases, the max is always the cell to the left. Am I right?
This is because you would want to carry the last matched character in both the strings. We would take the maximum between the top and the left because then that would mean that you are selecting the length of the two possible subsequences.
Your intuition is correct. L[i][0] or L[0][j] is for the cases of either string being empty i.e., one of them is empty string so common subsequence length is 0. This addition adds an extra row and column. So L[i][j] actually refers to the strings ending at X[i-1] and Y[j-1]. Hence we compare those.
I didn't get what you meant by 4 is not max in top and left cell :/ !! 4 >3 though....please clear that. UPDATE : SHE SAYS...... IF THE CURRENT VALUE IS NOT THE MAXIMUM OF TOP AND LEFT CELL...which is ...IF THE CURRENT VALUE IS NOT THE *(MAXIMUM OF TOP AND LEFT CELL)*
Calm down. The table explanation is very clear to me. Think about what she said at @1:20, the table is just a way to capture the recursive calculation.
It is correct. The x and y are the two arrays which have the input chars and it starts from 0 index. The loop will reach that condition when both i and j are not equal to zero. i.e at i=j=1. So x[0] and y[0] will be compared and the result will be stored at the L[i][j] i.e L[1][1]=L[0][0]+1 and then L[1][2]=L[0][1]+1 ...if they match.
When I saw the article. I totally scared and thought to quit. But after seeing this video I understood everything pin pointedly. Excellent explanation. Thank you so much GeeksforGeeks.
It was hard to understand the concept of 2D table, I had to check from other sources and think hard. You have shown algo, but also explain better. Nonetheless Thanks
This is not the correct solution.I tried with different examples and I got wrong answer.Example check for 'aggtab' and 'gxtgayb' it should return 5 but it is returning 4.
i could see a lot of people complaining about the approach, and how she derived that. Please take a look at this czcams.com/video/ASoaQq66foQ/video.html and again come back to this video. Let me know if that did help And BTW Kanika Gautam is really bad at explaining. Other g4g faculties are fine.
Bhai ladki padha rhi hai kya usse algorithm pooch rhe tmlog... Whitehat junior ka scam na dekha tmlogo ne Kuch nahi aata hoga inko bhai. Galti se aagaya Mai bhi.🤦♂️
How is anyone supposed to think of this solution themselves?
I don't understand why all these algorithm videos never explain how to get the solution. It's always something random like "max of top and left cell" without ever explaining what those values are. It's like the people making these videos do not even understand themselves.
Geeks for geeks is a superb Place to learn CS concepts.
I totally agree. Having read some more, what I understand is this:
The matrix (or table) called LCS[][] created here to fill in the values works like this - row is the length of sequence L1 +1 and column is the length of sequence L2 +1.
Now if the value at i-1 (subtracting 1 because the matrix is 1 row and 1 column extra than the original lengths of the sequence) of L1 matches with value of j-1 at L2, it means we have a common subsequence (of length 1). Now if there is any sequence common prior to this character, then that would be at i-1 and j-1, i.e., at length less than the current of L1 and L2 (pre computed in LCS[][]). Hence the solution- LCS[i][j] = LCS[i-1][j-1] + 1.
If the character does not match, then either L1 has more characters (uptil i) matching L2 (uptil j-1) or vice versa. We choose whatever is the maximum of two.
Let me know if the explanation is not at its best.
ur comment got so many likes ,but still dont get you .the video was everything to me for the lcs problem, please ask with details.
Just look at the recurrence relation, you'll understand why.
EDIT: Refer to some other source, he doesn't explain what the subproblems are and only how to get to the solution.
I think you know the answer ... practice. I am also unable to understand but I think how dynamic programming should be approached is you will have to go through what we are trying to avoid here. In this case, repeated computation of same things while using recursion. Now we need to overcome this overhead by computing only once for each. We can keep track of how much match has happened before current iteration using a lookup table and proceed using those previous calculations. The best way to store the data of matches two strings is a matrix(2d array).
You just told us what to do, not why you did it.
@@StarGazerHere Um, what? She might as well be no techie hired by the team solely to record the video.
This is what 'guys' do I guess, insane remarks.
@@mitagavade7591 He isn't wrong, girls remembered all long English and History answers back at school too. Seems like they have better memory.
@@mitagavade7591 fight fight fight!!!! XD
don't pay attention to such comments
At 6:42 you can use that G. You say "1 came from the left cell" but it didn't. It is 1 because G matches G, and the diagonal was 0. You skip that G for no reason.
No, she's right. She counted the G you're talking about in the previous column. No G was skipped in the video.
Hello
Can u please explain
why u picked max(leftcell,upcell) when characters dont match
Why we have to increment value of diagonal by 1 when characters match.
did u just read it out aloud from wikipedia but with ur own example. Please explain the approach, so that we can understand how to think of similar problems.
Tanmay Misra This is a specific problem and not a general idea. If you're looking for the general concept the videos at the beginning of the playlist will help you out in understanding the approach.
And you still have people giving thumbs up :D
Approach comes from practice do more
Akhlesh soni In order to practice effectively, we need to understand the approach
@@TM-qc5oz you are right. I would suggest you to visit the article mentioned in the description to understand the aproach.
while traversing back from 4 at Y,A how to distinguish that it came diagonally or max(top, left)?
I was reading the explanation of how this works but I could not get properly how the table actually gets filled. This video hit the spot. Thanks!
hey can u please provide the code snippet for this video.along with how to print the longest common sub sequence string
Please do not forget to mention the time and space complexity of the algorithms that you teach, since it is just as important. Nice explanation by the way :)
you explain the procedure but did not explain how you came up with that procedure..
please explain that also so that we can think the algorithm that solve particular problem...
Simple thing bro
The table should be drawn in reverse i.e "AGGTAB" in row wise & "GXTXAYB" in column wise, after that if we wanna print the output by printing the matrix that would be the actual table. Thank you
Thank you so much for the short and clear explaination :)
what is the code to find the longest subsequence?
if there is more than one longest subsequence then what we will do?plese help us
Great Explanation...Thank You!
superb way of explaining..nd awesome ppt
Excellent explanation! It was very helpful. Thank You.
We're glad you found them useful, Vatsal. You're welcome! :)
What if their are two or more common sequences of same length???
If two sub seqeucnes are of same length then they get concatenated and that is the resulting answer or longest common sub sequence. clear ?
s1 = abc pqr abc
s2 = abc xyz abc
LCS = longest common subsequence is = abcabc.
There can be more lcs's our moto is to find the length and using the table we can find the different lcs also at the same time
Suppose thre are two longest common sub sequences like for example
String 1: abcde
String b: acbde
here longest commom subsequence is of length 4 i.e abde and acde
what will be the time complexity?
@Kanika, The video that you posted is same as DSA - Tabulation from GFG, why repeat?
Expectation from this video was to print the LCS or return a List , I don't see either mentioned in this video.
The video is great! I read a lot of articles do not see how to find out the largest common sub-sequence, but I saw your video, got it...thank you...thank you...thank you
We're glad that you found it useful.
Nice video, really well explained :)
Some videos are really good by i am seriously struggling with the ones by Kanika Gautam, she says a lot of stuff incorrectly, please get them made again by other faculty.
if both left and top has equal value then which one i choose......if i choose either one then is there any fault???
You can choose either of them. It was explained clearly over here 6:33. There is no fault it is perfectly alright.
*For everyone asking why the matrix is built this way* :
When you are using dynamic programming you need to understand the recursive algorithm you would like to optimize.
I'll explain the non-genius solution where you go letter by letter from the start of each string.
The DP answer will be built bottom-up which would make the table fill from the end of the string as the vid suggests.
In this case (x is L1, y = L2):
LCS = {
1 + LCS(i+1, j+1) ; IF x[i]==y[j]
max(LCS(i+1, j), LCS(i, j+1)) ; ELSE
}
This is the top-down approach.
Now if you would like to convert the recursive solution to a matrix you need to take a bottom-up approach. And so the algorithm will look as follows:
LCS = [N][M] // N = len(x), M = len(y)
if x[i]==y[j]:
LCS[i][j] = 1 + LCS[i-1][j-1]
else:
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
Note that the matrix has to have a initialization row and column where all values are 0 in order to have an answer for i-1 and j-1 in the first run.
So if you are coding you should also use the case:
if (x[i] == 0 || y[j] == 0) -> LCS[i][j] = 0
You can easily see the correlation between the recursive and the DP solutions.
Just keep practicing, it is a skill worth working for and not black magic (as some may feel after watching this video).
Why do we have to get the max of L[i-1][j] and L[i][j-1] if no commonality is found? Is it because of the 0's in the first row and column? Because for other cases, the max is always the cell to the left. Am I right?
This is because you would want to carry the last matched character in both the strings. We would take the maximum between the top and the left because then that would mean that you are selecting the length of the two possible subsequences.
What is cost of lcs?
Nice explanation. Really made it simple to learn and code.
Thanks Snehashish!
Thank you for this video. Made my day!
Thanks Subhash for the appreciation!
@@GeeksforGeeksVideos lol
If we want to print the sub sequence, what should we do
log the output in console
Thank you so much !
why didnt u show the thought process
at 5:09 LCS[i-1][j] is top cell and LCS[i][j-1] is left cell
can you please post the algorithm to find the sequnce also :);
anyway thanks for explaining in such a simple way;
hackdown cinema adda I second that
If you are asking about the printing of the subsequence, you can fund it here: www.geeksforgeeks.org/printing-longest-common-subsequence/
Thank you for the explanation
Thanks RebelutionaryGaming
I think the else if condition should be "else if (X[i] == Y[j])", right?
Rohan Shah Nope, since you're assigning 0's to the 0th column and 0th row, It'll be i-1 and j-1
Your intuition is correct. L[i][0] or L[0][j] is for the cases of either string being empty i.e., one of them is empty string so common subsequence length is 0. This addition adds an extra row and column.
So L[i][j] actually refers to the strings ending at X[i-1] and Y[j-1]. Hence we compare those.
thanks for this video..
Thank you for explaining those algorithms so simply! 😀
Very Useful ...Thank you so much
We're glad that you found it useful.
wonderfully explained! Thank you! :-)
You're welcome, Sunil!
@@GeeksforGeeksVideos ur explanation is bullshit
Thanks a lot!!!
Superb explanation
I didn't get what you meant by 4 is not max in top and left cell :/ !! 4 >3 though....please clear that.
UPDATE :
SHE SAYS...... IF THE CURRENT VALUE IS NOT THE MAXIMUM OF TOP AND LEFT CELL...which is ...IF THE CURRENT VALUE IS NOT THE *(MAXIMUM OF TOP AND LEFT CELL)*
4 > 3 does not mean 4 is max(3, 3) . max(3, 3) is 3.
Yashwanth Soodini yes i understood it later and updated in comments as well :)
Calm down. The table explanation is very clear to me. Think about what she said at @1:20, the table is just a way to capture the recursive calculation.
Mam i think there is a mistake in your algorithm....in the second IF condition (x[i]==y[j]) not ( x[ i-1]==y[j-1] ).
It is correct. The x and y are the two arrays which have the input chars and it starts from 0 index. The loop will reach that condition when both i and j are not equal to zero. i.e at i=j=1. So x[0] and y[0] will be compared and the result will be stored at the L[i][j] i.e L[1][1]=L[0][0]+1 and then L[1][2]=L[0][1]+1 ...if they match.
Thanks,I got it.
When I saw the article. I totally scared and thought to quit. But after seeing this video I understood everything pin pointedly. Excellent explanation. Thank you so much GeeksforGeeks.
This is great, GeeksforGeeks is great! Please keep going.
~A genuine learner.
Thanks❤️
gotta give credit for using dark mode all the way
TY
It was hard to understand the concept of 2D table, I had to check from other sources and think hard. You have shown algo, but also explain better. Nonetheless Thanks
Even i can read the slides.
At least for me, Memoization with DepthFirstSearch solution for Longest Common Subsequence is much easier to understand
there are another approach that have o(n) time complexity and better understandable.
Where n is ?
Explanation is awasome.but written part that shown in screen that is so distrubing.that is not neccssary to add.
Very good explanation which is easy to follow and saves a lot of time. Well done Kanika!!!
M I supposed to learn the algorithm...where is the logic..
Very nice video! Well Done.
Thanks Νικόλας Μαυρογενειάδης :)
Awesome Explanation!!
Thanks Amber Kumar!
This is not the correct solution.I tried with different examples and I got wrong answer.Example check for 'aggtab' and 'gxtgayb' it should return 5 but it is returning 4.
4 hi return krna chahiye. algo is correct
Thanks nice tutorial
Thanks Abdul Ahad SHAIKH :)
i could see a lot of people complaining about the approach, and how she derived that. Please take a look at this czcams.com/video/ASoaQq66foQ/video.html and again come back to this video.
Let me know if that did help
And BTW Kanika Gautam is really bad at explaining. Other g4g faculties are fine.
Bhai ladki padha rhi hai kya usse algorithm pooch rhe tmlog...
Whitehat junior ka scam na dekha tmlogo ne
Kuch nahi aata hoga inko bhai.
Galti se aagaya Mai bhi.🤦♂️
Love your Indian accent.
sweet n short
Thank you, Shiva! :)