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.

- Create a matrix of the size of the both strings
`(n+1) * (m+1)`

and fill the first column and row with 0. - Now we have to keep filling this matrix by using following logic.
- 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.
- If it does not matches then fill the cell by taking max of its previous row and column’s value.
- Repeat this for all the rows and columns of the matrix.
- The last cell in the matrix (last row and last column) will have the length of the longest common subsequence.
- 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"]