Longest Common Subsequence

Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem is a classical problem in computer science and dynamic programming. The goal is to find the longest sequence that appears in both strings in the same order, but not necessarily consecutively.

Problem Statement:

Given two strings, X and Y, we need to find the length of the longest subsequence common to both strings. A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example:

Consider the two strings:

• X = "ABCBDAB"
• Y = "BDCABB"

The LCS of these two strings is "BDAB", which has a length of 4.

Approach:

The LCS problem can be solved efficiently using Dynamic Programming. We'll build a 2D table dp where dp[i][j] represents the length of the LCS of the first i characters of string X and the first j characters of string Y.

Dynamic Programming Recurrence:

1. Base Case:

   • dp[0][j] = 0 for all j (If one string is empty, the LCS length is 0).
   • dp[i][0] = 0 for all i (If the other string is empty, the LCS length is 0).

2. Recursive Case:

   • If X[i-1] == Y[j-1], then dp[i][j] = dp[i-1][j-1] + 1 (Include this character in the LCS).
   • If X[i-1] != Y[j-1], then dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (Exclude one character and check the maximum possible LCS from the two subproblems).

Steps:

1. Initialize a 2D DP table where the dimensions are (m + 1) x (n + 1) where m is the length of X and n is the length of Y.
2. Fill the DP table based on the recurrence relations.
3. The final solution will be stored in dp[m][n], which gives the length of the LCS of X and Y.

Time Complexity:

• Time Complexity: O(m * n), where m and n are the lengths of the two strings. This is because we fill a DP table of size (m + 1) x (n + 1).
• Space Complexity: O(m * n) for storing the DP table.

Implementation in C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to find the length of Longest Common Subsequence
int longestCommonSubsequence(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    // Create a 2D table to store lengths of longest common subsequence
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Build the dp table from the bottom up
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // If characters match, add 1 to the result from the previous characters
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // Otherwise, take the maximum of excluding one character from either string
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // dp[m][n] contains the length of the LCS
    return dp[m][n];
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCABB";

    cout << "Length of Longest Common Subsequence: " << longestCommonSubsequence(X, Y) << endl;

    return 0;
}

Explanation of Code:

1. Function longestCommonSubsequence(X, Y):

   • This function takes two strings X and Y and returns the length of their Longest Common Subsequence.
   • We initialize a 2D vector dp of size (m+1) x (n+1) to store the LCS lengths for different prefixes of the two strings.
   • We then fill the table using the recurrence relation:
     • If X[i-1] == Y[j-1], we increment the value from dp[i-1][j-1].
     • If X[i-1] != Y[j-1], we take the maximum of dp[i-1][j] and dp[i][j-1].
   • The value at dp[m][n] is the length of the LCS of X and Y.

2. Main function:

   • We call longestCommonSubsequence(X, Y) with two sample strings X and Y and print the result.

Example Run:

For the input strings:

X = "ABCBDAB"
Y = "BDCABB"

The DP table (dp) will be filled as follows (each cell represents the length of the LCS of the substrings up to that point):

		B	D	C	A	B	B
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	3
B	0	1	2	2	3	4	4
A	0	1	2	2	3	4	4

The length of the LCS is dp[7][6] = 4.

Backtracking to Find the LCS Sequence:

To actually retrieve the LCS string, we can backtrack from dp[m][n]:

1. Start from dp[m][n] and trace back to dp[0][0].
2. If X[i-1] == Y[j-1], then add X[i-1] to the LCS.
3. If X[i-1] != Y[j-1], move in the direction that gives the larger value (either move up or move left).

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string getLCS(string X, string Y) {
    int m = X.length();
    int n = Y.length();

    // DP table to store lengths of LCS
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Build the DP table
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Backtrack to find the LCS
    string lcs = "";
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            lcs = X[i - 1] + lcs;
            --i;
            --j;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }

    return lcs;
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCABB";

    cout << "Longest Common Subsequence: " << getLCS(X, Y) << endl;

    return 0;
}

Explanation of Backtracking:

• We start from dp[m][n] and move backward to reconstruct the LCS.
• If X[i-1] == Y[j-1], we add the character to the result and move diagonally (up-left).
• If X[i-1] != Y[j-1], we move in the direction that has the greater