Programming Interview Question: Longest Common Subsequence Dynamic Programming

Longest Common Subsequence (Dynamic programming)

Given two strings S1 and S2. Find the longest common subsequence between S1 and S2.

Example:-

S1 = "ACBEA"
S2 = "ADCA"

LCS = "ACA"

This video explains the solution to the Longest Common Subsequence with examples and visualization.

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[rishabhpandita]

nice explanation for quick revision of concepts. For people who are looking for more detail explanation please refer to Introduction to Algorithms
Book by Charles E. Leiserson, Clifford Stein, Ronald Rivest, and Thomas H. Cormen

[PoonamYadav-dhqz]

what exactly we will be storing in the pointer table? is it the character from the actual strings or the values like 'pick_s1' etc..

[goutkannan]

I guess there is a really minor bug in the code, consider the case s1= ABCDC, s2=BCDC. During the first iteration i=0 n j=0 s1[0] !=s2[0], the control goes to the else part but it does not have any implementation for such condition(i==0 n j==0) your code is saved by JVM's guarantee that upon using "new" array will be initialized with 0s. Any C/C++ programmers trying to learn from this code might be cursed by the evil GARBAGE. A mention of such a case in the video would clear this issue.

[suhasnayak]

You explained how it works, but it would be helpful if you can explain why it works ? why did you choose to solve this problem using DP ?

[AshishSharma-dgxg]

Well explained! but there is a corner case miss in the solution if the very first character is not matching, tried to get LCS for "SAPQRCDADEF" & "AABCADE" and the output is "SACADE" using same algo, need to add one more check i.e. if (S1.charAt(i) != S2.charAt(j)) and (i == 0 && j ==0), put match[i][j] = 0;

[suvamroy]

Is it KMP algorithm's LPS array calculation?

[akhilciricilla]

what if first elements of 2 strings are different?

[anujkumartarun]

What is logic to decide ACA is common substring ??

[ErfanHossainShoaib]

I tried to find all LCS by using pointer table but I failed. Please add a new video with a explanation how can we get all LCS.
Thank you.