Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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";
String B = "abcadf";
Longest Common Subsequence - example
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.
LCS Recursion Tree
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

 LCS Printing Result

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;
    }
    }