Longest Common Subsequence

return common subsequence largest length

Longest Common Subsequence

Problem Statement

You are given two strings, text1 and text2. Your goal is to return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence is a new string generated from the original string by deleting some characters (or none at all) without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence is simply a subsequence that appears in both strings.

Examples

Example 1

• Input: text1 = "abcde", text2 = "ace"
• Output: 3
• Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2

• Input: text1 = "abc", text2 = "abc"
• Output: 3
• Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3

• Input: text1 = "abc", text2 = "def"
• Output: 0
• Explanation: There is no such common subsequence, so the result is 0.

The Core Idea: String Comparison

We can solve this by comparing the two strings character by character, starting from their last indices (let's call them i and j).

At any given step, one of two things will happen:

1. The characters match (text1[i] === text2[j]): This means we have found a common character. We add 1 to our subsequence length and move both pointers backwards (i - 1 and j - 1) to check the remaining parts of the strings.
2. The characters do NOT match (text1[i] !== text2[j]): The longest common subsequence must come from either:
   • Skipping the current character in text1 and keeping text2 as is (i - 1, j).
   • Skipping the current character in text2 and keeping text1 as is (i, j - 1). We explore both paths and take the maximum result between the two.

Base Case: If either index falls below 0 (i < 0 or j < 0), it means we have completely exhausted one of the strings. At this point, no more common characters can be found, so we return 0.

Memoization (Top-Down Approach)

To prevent our recursive function from recalculating the same string combinations over and over, we use a 2D dp array.

• The state dp[i][j] will store the length of the longest common subsequence for the prefix of text1 up to index i and the prefix of text2 up to index j.
• Before doing any calculation, we check if dp[i][j] is already computed. If it is, we return it immediately.

Code Implementation

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
    // Initialize a 2D array for memoization
    let dp = Array.from({ length: text1.length }, () => Array(text2.length));
    
    function recurr(i, j) {
        // Base case: If either string is exhausted, the common length is 0
        if (i < 0 || j < 0) {
            return 0;
        }
        
        // If the result is already calculated, return it
        if (dp[i][j] !== undefined) {
            return dp[i][j];
        }
        
        // Match found: Add 1 and shrink both strings
        if (text1[i] === text2[j]) {
            dp[i][j] = 1 + recurr(i - 1, j - 1);
            return dp[i][j];
        }
        
        // Mismatch: Take the maximum of skipping a character from either string
        dp[i][j] = Math.max(recurr(i - 1, j), recurr(i, j - 1));
        
        return dp[i][j];
    }

    // Start checking from the last characters of both strings
    return recurr(text1.length - 1, text2.length - 1);
};

Tabulation

Since in base case we check for negative values we actually access negative values in an array so directly writing tabulation form will not be possible so we'll perform shifting of index where we'll just shift index by one position like this.

var longestCommonSubsequence = function (text1, text2) {

    let dp= Array.from({length:text1.length +1},()=>Array(text2.length +1))
    function recurr(i, j) {
        if(i==0 || j ==0){
            return 0;
        }
        if(dp[i][j]!==undefined){
            return dp[i][j]
        }
        if(text1[i-1] === text2[j-1]){
            dp[i][j]=1+ recurr(i-1,j-1)
          return dp[i][j]
        }
        dp[i][j]= Math.max(recurr(i-1,j), recurr(i,j-1))
        return dp[i][j]
    }

    return recurr(text1.length  , text2.length )
};

then we can introduce tabulation

var longestCommonSubsequence = function (text1, text2) {

    let dp = Array.from(
        { length: text1.length + 1 },
        () => Array(text2.length + 1).fill(0)
    );


    for (let i = 1; i <= text1.length; i++) {
        for (let j = 1; j <= text2.length; j++) {

            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    dp[i][j - 1]
                );
            }
        }
    }

    return dp[text1.length][text2.length];
};