# Longest Common Substring

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

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"`.

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. Longest Common Substring Step 1

• 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. Longest Common Substring Step 2

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. Longest Common Substring 3

and keep going till we reach the end of both strings which is the answer. Longest Common Substring 4

```/**
* @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);```