# Dynamic Programming — Longest Common Subsequence

Objec­tive: Given two string sequences, write an algo­rithm to find the length of longest sub­se­quence present in both of them.

These kind of dynamic pro­gram­ming ques­tions are very famous in the inter­views like Ama­zon, Microsoft, Ora­cle and many more.

What is Longest Com­mon Sub­se­quence: A longest sub­se­quence is a sequence that appears in the same rel­a­tive order, but not nec­es­sar­ily contiguous(not sub­string) in both the string.

Exam­ple:

```String A = "acbaed";

Longest Common Subsequence(LCS):     acad, Length: 4
```

Approach:

Recur­sion:

Start com­par­ing strings in reverse order one char­ac­ter at a time.

Now we have 2 cases -

1. Both char­ac­ters are same
1. add 1 to the result and remove the last char­ac­ter from both the strings and make recur­sive call to the mod­i­fied strings.
2. Both char­ac­ters are different
1. Remove the last char­ac­ter of String 1 and make a recur­sive call and remove the last char­ac­ter from String 2 and make a recur­sive and then return the max from returns of both recur­sive calls. see exam­ple below

Exam­ple:

```Case 1:

String A: "ABCD", String B: "AEBD"

LCS("ABCD", "AEBD") = 1 + LCS("ABC", "AEB")

Case 2:

String A: "ABCDE", String B: "AEBDF"

LCS("ABCDE", "AEBDF") = Max(LCS("ABCDE", "AEBD"), LCS("ABCD", "AEBDF"))
```

Code:

In a given string of length n, there can be 2n sub­se­quences can be made, so if we do it by recur­sion then Time com­plex­ity will O(2n) since we will solv­ing sub prob­lems repeat­edly.

Dynamic Pro­gram­ming:

We will solve it in Top-manner and store the solu­tion of the sub prob­lems in a solu­tion array and use it when ever needed, This tech­nique is called Mem­o­iza­tion. See the code for bet­ter explanation.

Code:

Print the Longest Com­mon Subsequence:

Take a look into the LCS[][] used in the code

Start from bot­tom right cor­ner and track the path and mark the cell from which cell the value is com­ing and when­ever you go diag­o­nal ( means last char­ac­ter of both string has matched, so we reduce the length of both the strings by 1, so we moved diag­o­nally), mark those cells, this is our answer.

Com­plete Code( Include Print­ing Result):

#### You may also like...

• Le Trong

Is it a typo in case 2 of the example?

• tuto­ri­al­hori­zon

Yes , cor­rected it , Thanks Le

• V Jain

In case 1 using recur­sive func­tion, can it be extended to print LCS as well?

• Kareiga Kamanda

What is the sim­i­lar­ity between 85.17.19.4.
2

• arc

How and why is your solu­tion top-down approach? You started at zero and reached the solu­tion step by step. Is it bottom-top approach?

• Paras

For beginner,you can check also below naive and sim­ple logic

pub­lic class LCSNaive {
pub­lic sta­tic void main(String[] args) {
String str1 = “ACBDEA”;
String str2 = “ABCDA”;
String result = lcs(str1, str2);
System.out.println(result);
}

sta­tic String lcs(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int j = 0, ji = 0;
String result = “”;
for (int i = 0; i < len1; i++) {
for (; j < len2; j++) {
if (str1.charAt(i) == str2.charAt(j)) {
result += str1.charAt(i);
ji = j;
break;
}
}
if (j == len2)
j = ji + 1;
}
return result;
}
}

• https://www.banglatime24.com Lin­coln Mahmud

It’s not work­ing with big string.

• Ankita

Thank you so much for the article 🙂

• Айдар Бариев

Hi SJ, looks like in “find” method we could skip two “for” cycles which set 0 into LCS array, because they are con­structed with 0 val­ues. Also, “String[][] solu­tion” vari­able pur­pose is not clear in that method, we could just omit it and result will be the same.

• http://thinkndoawesome.blogspot.com Shashi Kant

it’s bot­tom up approach ..