Table of Contents

## Task

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

## Solution

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);