Longest Common Subsequence

Concept

LeetCode #1143.
Problem: Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Input: text1 = "abcde", text2 = "ace"
Output: 3 (The LCS is "ace").

Input: text1 = "abc", text2 = "def"
Output: 0

We are no longer working with a single 1D array. We are comparing two entirely different strings.
Because we have two changing variables (the index in text1, and the index in text2), a 1D DP Array will not work. We must upgrade to a 2D DP Matrix.

The 2D DP Strategy

Let’s build a grid. text1 is the Rows. text2 is the Columns.
dp[r][c] will answer the question: “What is the LCS if we only look at the substring up to row r and the substring up to column c?”

The Magic Rules:
Imagine we are comparing the letter at text1[r] and text2[c].

1. They Match! (text1[r] === text2[c])
   We found a matching letter! The LCS mathematically increases by 1.
   We add 1 to whatever the LCS was BEFORE we found this letter. Where is that stored? Up and to the left! (Diagonal).
   dp[r][c] = 1 + dp[r - 1][c - 1]

2. They Do NOT Match! (text1[r] !== text2[c])
   They don’t match. We can’t add 1. We must just inherit the best score we had previously.
   We have a choice: We can drop the current letter from text1 (Look Up), or drop the current letter from text2 (Look Left). We take the maximum of both.
   dp[r][c] = Math.max(dp[r - 1][c], dp[r][c - 1])

Implementation (Tabulation)

Because we look “Up” and “Left”, we initialize the Matrix with an extra row of 0s at the top, and an extra column of 0s on the left. This represents comparing against an empty string "" (which trivially has an LCS of 0) and perfectly prevents Out of Bounds array errors!

// Time Complexity: O(M * N)
// Space Complexity: O(M * N) (The 2D Matrix)

function longestCommonSubsequence(text1: string, text2: string): number {
    const rows = text1.length;
    const cols = text2.length;

    // 1. Create the (M+1) x (N+1) DP Matrix, filled with 0s
    // WARNING: Do not use .fill(new Array()). Use Array.from!
    const dp = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));

    // 2. Loop through the grid
    for (let r = 1; r <= rows; r++) {
        for (let c = 1; c <= cols; c++) {
            
            // Notice we do [r-1] and [c-1] when reading from the strings,
            // because the DP grid is shifted by +1 to hold the buffer zeroes!
            if (text1[r - 1] === text2[c - 1]) {
                // RULE 1: They match! Diagonal + 1.
                dp[r][c] = 1 + dp[r - 1][c - 1];
            } else {
                // RULE 2: No match. Max of Up vs Left.
                dp[r][c] = Math.max(dp[r - 1][c], dp[r][c - 1]);
            }
        }
    }

    // The absolute bottom-right corner holds the final answer for the full strings
    return dp[rows][cols];
}

Advanced State Reduction ($O(N)$ Space)

Can we optimize a massive 2D matrix? Yes!
Look at the Recurrence Relations:

• dp[r - 1][c - 1] (Diagonal Up-Left)
• dp[r - 1][c] (Directly Above)
• dp[r][c - 1] (Directly Left)

The math NEVER looks further back than exactly 1 row above.
Therefore, we don’t need a massive 1000x1000 matrix in RAM. We only need Two 1D Arrays: previousRow and currentRow.
As we iterate, we overwrite previousRow with currentRow. This drops the Space Complexity from $O(M \times N)$ to $O(N)$!

Interview Questions

Q: “Edit Distance” (LeetCode 72) asks for the minimum operations (Insert, Delete, Replace) to convert word1 into word2. Is this the same algorithm?
A: Yes, it uses the exact same 2D DP Matrix setup! The rules just change slightly.
If they match: dp[r][c] = dp[r-1][c-1] (No cost).
If they don’t match, you take 1 + Math.min of the three options:

• Insert: Look Left (dp[r][c-1])
• Delete: Look Up (dp[r-1][c])
• Replace: Look Diagonal (dp[r-1][c-1]).

Q: A problem asks for the “Longest Palindromic Subsequence”. How do you solve it?
A: It is a brilliant trick. You take the input string s. You reverse it to create sReverse. You then pass both strings exactly into the longestCommonSubsequence(s, sReverse) function! The LCS of a string and its reverse is mathematically guaranteed to be its longest palindrome.