Longest common subsequence | Print all LCS

Given a set of strings (in our case two) find the longest common subsequence between them and if found print them all.

A subsequence of a string is new string (which can be empty) that is generated from the original string by deleting some characters of it while maintaining the relative order of it.

For example "ace" is subsequence of "abcde".

A common subsequence between two or more strings is the subsequence which is present in all the strings.

Input:
"ABCD"
"ACBAD"

Output:
3
"ABD"
"ACD"

In the previous post, we have seen how to find the longest common sequence in this post we will see how to print them.

Using the following steps and matrix we can find all the lcs and print them.

1. Create a matrix of the size of the both strings (n+1) * (m+1) and fill the first column and row with 0.
2. Now we have to keep filling this matrix by using following logic.
3. Traverse both the strings and if the character at the current column and row matches then fill that cell by adding 1 to the value of its left top diagonal element.
4. If it does not matches then fill the cell by taking max of its previous row and column’s value.
5. Repeat this for all the rows and columns of the matrix.
6. The last cell in the matrix (last row and last column) will have the length of the longest common subsequence.
7. To find the longest common subsequence, start from the last element and trace its path back, determine from where the value of the current is derived from and include the current cell character when you change the row.

Longest common subsequence print any one.

const LCS = (str1, str2, m = str1.length, n = str2.length, T) => {
  // base case: return an empty string when there is no more subsequence to examine
  if (m === 0 || n === 0) {
    return "";
  }

  // if the character at the given indexes of str1 and str2 matches
  if (str1[m - 1] === str2[n - 1]){
    // add the current character to the subsequence.
    return LCS(str1, str2, m - 1, n - 1, T) + str1[m - 1];
  }

  // else
  // if the previous column has more value
  if (T[m - 1][n] > T[m][n - 1]) {
    return LCS(str1, str2, m - 1, n, T);
  }
  else {
    // if the previous row has more value 
    return LCS(str1, str2, m, n - 1, T);
  }
}
 
// Fill the matrix by finding the length of LCS
const LCSLength = (str1, str2, m = str1.length, n = str2.length, T) => {
  // fill the matrix in a bottom-up manner
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // if character at the given indexes of str1 and str2 matches
      if (str1[i - 1] === str2[j - 1]) {
        T[i][j] = T[i - 1][j - 1] + 1;
      }
      // else,
      else {
        T[i][j] = Math.max(T[i - 1][j], T[i][j - 1]);
      }
    }
  }
}

Input:
const str1 = "XMJYAUZ", str2 = "MZJAWXU";
const m = str1.length;
const n = str2.length;

const T = new Array(m + 1);
for(let i = 0; i < T.length; i++){
  T[i] = new Array(n + 1).fill(0);
}
 
// fill lookup table
LCSLength(str1, str2, m, n, T);

// find the longest common sequence
console.log(LCS(str1, str2, m, n, T));

Output:
"MJAU"

---

Longest common subsequence print all.

To print all the lcs we will use an array to track all the possible path.

// Fill the matrix by finding the length of LCS
const LCSLength = (str1, str2, m = str1.length, n = str2.length, T) => {
  // fill the matrix in a bottom-up manner
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // if character at the given indexes of str1 and str2 matches
      if (str1[i - 1] === str2[j - 1]) {
        T[i][j] = T[i - 1][j - 1] + 1;
      }
      // else,
      else {
        T[i][j] = Math.max(T[i - 1][j], T[i][j - 1]);
      }
    }
  }
}

const LCS = (str1, str2, m = str1.length, n = str2.length, T) => {
  
  // base case: no more characters to examine
  if (m === 0 || n === 0) {
    // return an array with single empty string
    return [""];
  }

  // if the character for both the string matches
  if (str1[m - 1] === str2[n - 1]) {
    
    // find the lcs for remaining characeters
    let lcs = LCS(str1, str2, m - 1, n - 1, T);
    
    // add the character to subsequence
    for (let i = 0; i < lcs.length; i++) {
      lcs[i] = lcs[i] + str1[m-1];
    }
    
    return lcs;
  }

  // else, when characters do not match
  
  // top cell of the current cell is greater than left cell,
  // check for the next character of str1
  if (T[m - 1][n] > T[m][n - 1]) {
    return LCS(str1, str2, m - 1, n, T);
  }

  // left cell of the current cell is greater than top cell,
  // check for the next character of str2
  if (T[m][n - 1] > T[m - 1][n]) {
    return LCS(str1, str2, m, n - 1, T);
  }

  // if both the cell are equal consider them both
  let top = LCS(str1, str2, m - 1, n, T);
  let left = LCS(str1, str2, m, n - 1, T);
  
  //merge them
  top = [...top, ...left];
  
  return top;
}

const LCSSet = (str1, str2, T) => {
  // fill the matrix to track the lcs
  LCSLength(str1, str2, str1.length, str2.length, T);
    
  // find all the lcs
  const lcs = LCS(str1, str2, str1.length, str2.length, T);

  //return the unique
  return [...new Set(lcs)];
}

Input:
const str1 = "ABCBDAB", str2 = "BDCABA";
const m = str1.length;
const n = str2.length;

//Fill the matrix
const T = new Array(m + 1);
for(let i = 0; i < T.length; i++){
  T[i] = new Array(n + 1).fill(0);
}

// find the longest common sequence
console.log(LCSSet(str1, str2, T));

Output:
["BCBA","BCAB","BDAB"]