Longest Common Subsequence (LCS)

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. LeetCode - Longest Common Subsequence

Approach

Let i and j be indices in text1 and text2, respectively. Define f(i, j) as the length of LCS of substrings text1[0..i-1] and text2[0..j-1].

Recurrence Relation:

Copyf(i, j) =
    1 + f(i-1, j-1)         if text1[i-1] == text2[j-1]
    max(f(i-1, j), f(i, j-1)) otherwise

Brute Force (Recursion)

Exponential time: O(2^n)

Copyint lcsRecursive(const string& text1, const string& text2, int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (text1[i - 1] == text2[j - 1])
        return 1 + lcsRecursive(text1, text2, i - 1, j - 1);
    else
        return max(lcsRecursive(text1, text2, i - 1, j), lcsRecursive(text1, text2, i, j - 1));
}

int longestCommonSubsequence(string text1, string text2) {
    return lcsRecursive(text1, text2, text1.size(), text2.size());
}

Memoization (Top-down DP)

Time: O(n * m), Space: O(n * m) (for memo)

Copyint lcsMemo(vector<vector<int>>& dp, const string& text1, const string& text2, int i, int j) {
    if (i == 0 || j == 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];

    if (text1[i - 1] == text2[j - 1])
        return dp[i][j] = 1 + lcsMemo(dp, text1, text2, i - 1, j - 1);
    else
        return dp[i][j] = max(lcsMemo(dp, text1, text2, i - 1, j), lcsMemo(dp, text1, text2, i, j - 1));
}

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size(), m = text2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
    return lcsMemo(dp, text1, text2, n, m);
}

Tabulation (Bottom-up DP)

Time: O(n * m), Space: O(n * m)

Copyint longestCommonSubsequence(string text1, string text2) {
    int n = text1.size(), m = text2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (text1[i - 1] == text2[j - 1])
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[n][m];
}

Space-Optimized DP

Space: O(min(n, m))

Copyint longestCommonSubsequence(string text1, string text2) {
    if (text2.size() > text1.size()) swap(text1, text2);  // Ensure text1 is longer

    int n = text1.size(), m = text2.size();
    vector<int> prev(m + 1, 0), curr(m + 1, 0);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (text1[i - 1] == text2[j - 1])
                curr[j] = 1 + prev[j - 1];
            else
                curr[j] = max(prev[j], curr[j - 1]);
        }
        prev = curr;
    }

    return prev[m];
}

Summary