Longest Common Subsequence Solution

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to given two sequences.

LCS problem is used to determine how similar the two DNA strands are. For instance

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Naive Approach

The naive solution will be to generate all subsequences of given sequences and then compare them to find the longest matching subsequence. It is exponential in time complexity. Because number of subsequences of a string having n characters is : 2ⁿ – 1 (since choice is either to select a given character or not).

However, this problem could be solved in polynomial time by Dynamic Programming.

Optimal Substructure

Let X = {X1, X2, X3,..Xm} and Y = {Y1, Y2, Y3,….Yn} be the two sequences and let

Let X = {X1, X2, X3,..Xm} and Y = {Y1, Y2, Y3,….Yn} be the two sequences and, 

Let LCS[i][j] be the LCS of given sequences:
1. If X[i-1] == Y[j-1], then LCS[i][j] = LCS[i-1][j-1] + 1
   (adding 1 to the length of the longest subsequence till i-2th & j-2th string
   characters, if X[i-1] == Y[j-1])
2. Else LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

Code Implementation

//
//  main.cpp
//  Longest Common Subsequence
//
//  Created by Himanshu on 17/09/21.
//

#include <iostream>

#include <iostream>
using namespace std;

void LCS (string s1, string s2) {
    int N = (int)s1.size(), M = (int)s2.size();
    int L[N+1][M+1];

    for (int i=0; i<=N; i++) {
        for (int j=0; j<=M; j++) {
            L[i][j] = 0;
        }
    }

    for (int i=0; i<=N; i++) {
        for (int j=0; j<=M; j++) {
            if (i == 0 || j == 0) {
                L[i][j] = 0;
            } else if (s1[i-1] == s2[j-1]) {
                L[i][j] = L[i-1][j-1] + 1;
            } else {
                L[i][j] = max(L[i][j-1], L[i-1][j]);
            }
        }
    }
    
    cout<<"Length of Longest Common Subsequence (LCS) is: "<<L[N][M]<<endl;
    
}
 
int main() {
    string s1 = "abcde", s2 = "ace";
    LCS(s1, s2);
}

Output:

Length of Longest Common Subsequence (LCS) is: 3

Here’s a working example: Ideone