Print Longest Common Subsequence (LCS)

Problem Statement

Given two strings text1 and text2, return any one Longest Common Subsequence (LCS) between them.

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

If multiple LCS solutions exist, return any one of them.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist only of lowercase english letters

Examples

Example 1:

Input: text1 = "abcde"
       text2 = "ace"

Output: "ace"

Explanation: "ace" is the longest common subsequence.

Example 2:

Input: text1 = "aggtab"
       text2 = "gxtxayb"

Output: "gtab"

Explanation: "gtab" is one valid LCS. Other valid outputs (if same length) would also be accepted.

Example 3:

Input:
 text1 = "abc"
       text2 = "def"

Output:
 ""

Explanation:
There is no common subsequence. Return an empty string.

Different Approaches

1️⃣ Recursive Approach

Code:

#include <iostream>
#include <string>
using namespace std;

string lcsRecursive(string text1, string text2, int i, int j) {
    // Base case: if either string is fully traversed
    if (i == text1.length() || j == text2.length()) {
        return "";
    }

    // If characters match, include this character and move diagonally
    if (text1[i] == text2[j]) {
        return text1[i] + lcsRecursive(text1, text2, i + 1, j + 1);
    } else {
        // Else, explore both options: skip from text1 or skip from text2
        string option1 = lcsRecursive(text1, text2, i + 1, j);
        string option2 = lcsRecursive(text1, text2, i, j + 1);

        // Return the longer of the two options
        return (option1.length() > option2.length()) ? option1 : option2;
    }
}

string printLongestCommonSubsequence(string text1, string text2) {
    return lcsRecursive(text1, text2, 0, 0);
}

int main() {
    string s1 = "abcde";
    string s2 = "ace";

    string res = printLongestCommonSubsequence(s1, s2);
    cout << res << endl; // Output: ace

    return 0;
}

Complexity Analysis:

• Time Complexity:O(2 ^ (min(s1.length()), s2.length()))
• Space Complexity:O(min(s1.length(), s2.length())

2️⃣ Memoization

Code:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string lcsMemo(string& text1, string& text2, int i, int j, vector<vector<string>>& dp) {
    // Base case
    if (i == text1.length() || j == text2.length()) {
        return "";
    }

    // If already computed, return from memo table
    if (!dp[i][j].empty()) {
        return dp[i][j];
    }

    // If characters match, include it and move diagonally
    if (text1[i] == text2[j]) {
        dp[i][j] = text1[i] + lcsMemo(text1, text2, i + 1, j + 1, dp);
    } else {
        // Explore both options and take longer one
        string option1 = lcsMemo(text1, text2, i + 1, j, dp);
        string option2 = lcsMemo(text1, text2, i, j + 1, dp);

        dp[i][j] = (option1.length() > option2.length()) ? option1 : option2;
    }

    return dp[i][j];
}

string printLongestCommonSubsequence(string text1, string text2) {
    int l1 = text1.length();
    int l2 = text2.length();

    // Initialize memoization table with empty strings
    vector<vector<string>> dp(l1, vector<string>(l2, ""));

    return lcsMemo(text1, text2, 0, 0, dp);
}

int main() {
    string s1 = "abcde";
    string s2 = "ace";

    string res = printLongestCommonSubsequence(s1, s2);
    cout << res << endl; // Output: ace

    return 0;
}

Complexity Analysis:

• Time Complexity:O(l1 * l2 * min(l1, l2))
• Space Complexity:O(l1 * l2 * min(l1, l2))

3️⃣ Tabulation

Code:

string printLongestCommonSubsequence(string text1, string text2) {
    // Step 1: Get lengths of the input strings
    int l1 = text1.length();
    int l2 = text2.length();

    // Step 2: Initialize a 2D dp table where dp[i][j] holds the LCS of
    // text1[0...i-1] and text2[0...j-1]. Initialize all values to empty strings.
    vector<vector<string>> dp(l1 + 1, vector<string>(l2 + 1, ""));

    // Step 3: Fill the dp table using bottom-up dynamic programming
    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {

            // Case 1: Characters match, so include this character in the LCS
            if (text1[i - 1] == text2[j - 1]) {
                // Add the current matching character to the LCS of previous indices
                dp[i][j] = dp[i - 1][j - 1] + text1[i - 1]; // Correct order: left-to-right
            } 
            // Case 2: Characters don't match, take the longer LCS from previous subproblems
            else {
                string option1 = dp[i - 1][j]; // Skip character from text1
                string option2 = dp[i][j - 1]; // Skip character from text2

                // Choose the option that gives a longer LCS
                dp[i][j] = (option1.length() > option2.length()) ? option1 : option2;
            }
        }
    }

    // Step 4: The bottom-right cell contains the final LCS string
    return dp[l1][l2];
}

Complexity Analysis:

• Time Complexity:O(l1 * l2 * min(l1, l2))
• Space Complexity:O(l1 * l2 * min(l1, l2))
  • No recursion stack