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

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

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

A common subsequence of two strings is a subsequence that is common to both strings.

 

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.

 

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

This problem was taken from Leetcode Longest Common Subsequence

 

Dynamic programming with memoization.

We create a matrix to store (memoize) the response from previous calculations so we won’t re-calculate them again.

We are starting from the first row comparing every character from column 1 with the first character from row one.

There are two cases:

• either the character match, then we add 1 and add it with the value from the diagonal to the left of the cell where we are.

• the characters don’t match, then we get the MAX of the value above current cell  and the value to the left of the current cell.

Here again c int the column (first string) matches c in the row (the second string)

so we get the value of last comparison (to the left and up diagonal of the current cell)  which is 1 and add 1 again since characters match.

and keep going till we reach the end of both strings which is the answer.

 

 

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    var txt1 = text1.split('');
    var txt2 = text2.split('');

    txt1.unshift('0');
    txt2.unshift('1');

    var l1 = txt1.length;
    var l2 = txt2.length;

    var matrix = [];
    for(var i = 0; i < l2; i ++) {
        matrix[i] = new Array(l1).fill(0);
    }

    var maxCommon = 0;
    
    for(var row = 0; row < l2; row ++) {
        for(var col = 0; col < l1; col ++) {
            var last = 0;

            if(txt1[col] == txt2[row]) {
                var previousDiagonalRowVal = row == 0 || col == 0  ? 0 : matrix[row - 1][col - 1];
                last =  1 + previousDiagonalRowVal;
            }
            else {
                var prevUp = row == 0 ?  0 : matrix[row - 1][col];
                var prevLeft = col == 0 ? 0 : matrix[row][col - 1];               
                last = Math.max(prevUp, prevLeft);
            }
            matrix[row][col] = last;
            maxCommon = last > maxCommon ? last : maxCommon;
    
        }
    }    
    return maxCommon;
};

var text1 = "abcde", text2 = "ace";
var r = longestCommonSubsequence(text1, text2);
console.log(">>", r);