Longest Common Subsequence

How it works

We can reduce space further by using a single array and a temporary variable. When iterating right to left within a row, we need the old value at position j (which becomes dp[i+1][j] in 2D terms) before overwriting it. We store this in a variable prev before the update, then use it for the diagonal reference in the next iteration.

Steps

1. If text1 is shorter, swap strings for minimal space.
2. Initialize a single array dp of size n+1.
3. Iterate i from m-1 down to 0:
   • Set prev = 0 (represents dp[i+1][n]).
   • For each j from n-1 down to 0:
     • Save temp = dp[j] (the old value before update).
     • If characters match, set dp[j] = 1 + prev.
     • Otherwise, set dp[j] = max(dp[j], dp[j+1]).
     • Update prev = temp.
4. Return dp[0].

Complexity

• Time complexity: O(m * n)
• Space complexity: O(min(m, n))

Where m is the length of the string text1 and n is the length of the string text2.

Things to watch for

Confusing Subsequence with Substring

A subsequence does not require consecutive characters, whereas a substring does. A common mistake is to reset the count when characters do not match, which would find the longest common substring instead of subsequence. In LCS, when characters do not match, you take the maximum of skipping either character.

Off-by-One Errors in DP Table Indexing

When using a 2D DP table, the dimensions should be (m+1) x (n+1) to account for the base case of empty strings. Accessing dp[i+1][j+1] when characters match requires careful attention to avoid index out of bounds errors.

Incorrect Iteration Direction in Bottom-Up DP

In the bottom-up approach, iterating in the wrong direction can cause the algorithm to use uncomputed values. When processing from the end of the strings backward, ensure that dp[i][j] is computed after dp[i+1][j+1], dp[i+1][j], and dp[i][j+1] are already available.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) < len(text2):
            text1, text2 = text2, text1

        dp = [0] * (len(text2) + 1)

        for i in range(len(text1) - 1, -1, -1):
            prev = 0
            for j in range(len(text2) - 1, -1, -1):
                temp = dp[j]
                if text1[i] == text2[j]:
                    dp[j] = 1 + prev
                else:
                    dp[j] = max(dp[j], dp[j + 1])
                prev = temp

        return dp[0]

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if (text1.size() < text2.size()) {
            swap(text1, text2);
        }

        vector<int> dp(text2.size() + 1, 0);

        for (int i = text1.size() - 1; i >= 0; --i) {
            int prev = 0;
            for (int j = text2.size() - 1; j >= 0; --j) {
                int temp = dp[j];
                if (text1[i] == text2[j]) {
                    dp[j] = 1 + prev;
                } else {
                    dp[j] = max(dp[j], dp[j + 1]);
                }
                prev = temp;
            }
        }

        return dp[0];
    }
};