# Longest common subsequence problem in JavaScript

In this problem, we need to find the longest common subsequence (lcs) between 2 strings and return the size of it.

Example:

```javascript```let string_1 = 'ddErik';
let string_2 = 'Emrlik';

// Longest common subsequence is 'Erik'
// Length of it is 4
``````

To find the longest common subsequence it's convenient to build a matrix with the strings as axes:

```terminal```    d d E r i k
E   - - - - - -
m   - - - - - -
r   - - - - - -
l   - - - - - -
i   - - - - - -
k   - - - - - -
``````

## First row

Now let's fill the first row:

```terminal```    d
E   0

string_1 = 'E'
string_2 = 'd'
lcs      = 0
``````

Next element:

```terminal```    d d
E   0 0

string_1 = 'E'
string_2 = 'dd'
lcs      = 0
``````

Next element:

```terminal```    d d E
E   0 0 1

string_1 = 'E'
string_2 = 'ddE'
lcs      = 1
``````

Next element:

```terminal```    d d E r
E   0 0 1 1

string_1 = 'E'
string_2 = 'ddEr'
lcs      = 1
``````

We can continue and fill the whole row:

```terminal```    d d E r i k
E   0 0 1 1 1 1
``````

## First column

We can do the same process as before but with the first column:

```terminal```    d
E   0
m   0

string_1 = 'Em'
string_2 = 'd'
lcs      = 0
``````

Next element:

```terminal```    d
E   0
m   0
r   0

string_1 = 'Emr'
string_2 = 'd'
lcs      = 0
``````

Finally:

```terminal```    d
E   0
m   0
r   0
l   0
i   0
k   0
``````

## Rest of the matrix

We can do the same with the rest of the matrix:

```terminal```    d d E r i k
E   0 0 1 1 1 1
m   0 0 - - - -

string_1 = 'Em'
string_2 = 'dd'
lcs      = 0
``````

Next element:

```terminal```    d d E r i k
E   0 0 1 1 1 1
m   0 0 1 - - -

string_1 = 'Em'
string_2 = 'ddE'
lcs      = 1
``````

If you fill the matrix by hand, you'll get:

```terminal```    d d E r i k
E   0 0 1 1 1 1
m   0 0 1 1 1 1
r   0 0 1 2 2 2
l   0 0 1 2 2 2
i   0 0 1 2 3 3
k   0 0 1 2 3 4
``````

Notice a pattern here between `string_1` and `string_2`:

1. If both strings end with same char:

`lcs = matrix[row - 1][column - 1] + 1`

2. If both strings end with different char:

`lcs = max(matrix[row - 1][column], matrix[row][column - 1])`

## Let's write the code

```javascript```function commonChild(s1, s2) {

// Initializing longest common subsequence to 0
let lcs = 0;

// Initializing the matrix
let matrix = Array(s1.length).fill('-').map(e => Array(s2.length).fill('-'));

// We are building a matrix such as:
//
//      d d E r i k
//  E   0 0 1 1 1 1
//  m   0 0 1 1 1 1
//  r   0 0 1 2 2 2
//  l   0 0 1 2 2 2
//  i   0 0 1 2 3 3
//  k   0 0 1 2 3 4
//

// Filling first element of the matrix
matrix = s1 === s2 ? 1 : 0;

// Filling first row and column
for(let i = 1; i < s1.length; i ++){

matrix[i] = s1[i] === s2 ? 1 : matrix[i - 1];
matrix[i] = s1 === s2[i] ? 1 : matrix[i - 1];

}

// Filling the rest of the matrix
for(let i = 1; i < s2.length; i++){
for(let j = 1; j < s1.length; j++){

// First condition
if(s1[j] === s2[i])
matrix[i][j] = matrix[i - 1][j - 1] + 1;
// Second condition
else
matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1]);

// Updating max lcs
lcs = matrix[i][j] > lcs ? matrix[i][j] : lcs;

}

}

// Returning result
return lcs;

}
`````` Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.