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[0][0] = s1[0] === s2[0] ? 1 : 0;
    
    // Filling first row and column
    for(let i = 1; i < s1.length; i ++){
        
        matrix[0][i] = s1[i] === s2[0] ? 1 : matrix[0][i - 1];
        matrix[i][0] = s1[0] === s2[i] ? 1 : matrix[i - 1][0];
        
    }
    
    // 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;
    
}