The longest common subsequence (LCS) problem is the problem of finding the longest subsequence that is present in given two sequences in the same order. i.e. find a longest sequence which can be obtained from the first original sequence by deleting some items, and from the second original sequence by deleting other items.

**Prerequisite:** Longest Common Subsequence | Introduction & LCS Length

In previous post, we have discussed Longest Common Subsequence of two sequences. In this post, we will extend the solution to three sequences. The proposed solution can be easily generalized to handle more than three sequences as well.

For example, consider the three following sequences X, Y and Z

X: ABCBDAB

Y: BDCABA

Z: BADACB

The length of LCS is 4 and LCS is BDAB

We have seen in the previous post, LCS problem has an optimal substructure which means that the main problem can be broken down into smaller, simple “subproblems”, which can further be divided into yet simpler subproblems..

1. Let us consider given sequences X, Y and Z of length i, j and k that both end in the same element. To find their LCS, shorten each sequence by removing the last element, find the LCS of the shortened sequences, and to that LCS append the removed element. So if X[i] = Y[j] = Z[k], we can say that,

2. Now suppose that the given sequences do not end in the same symbol. Then the LCS of X, Y, Z is the longer of the given sequences

LCS(X[1..i], Y[1..j-1], Z[1..k]) and

LCS(X[1..i], Y[1..j], Z[1..k-1])

.

Below solution finds the length of LCS of sequences X[0..m-1], Y[0..n-1] and Z[0..o-1] recursively by using optimal substructure property of LCS problem.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <bits/stdc++.h> using namespace std; // Function to return maximum of three integers int max(int a, int b, int c) { return max(max(a, b), c); } // Function to find length of Longest Common Subsequence of // sequences X[0..m-1], Y[0..n-1] and Z[0..o-1] int LCSLength(string X, string Y, string Z, int m, int n, int o) { // return if we have reached the end of either sequence if (m == 0 || n == 0 || o == 0) return 0; // if last character of X, Y, Z matches if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1]) return LCSLength(X, Y, Z, m - 1, n - 1, o - 1) + 1; // else if last character of X, Y, Z don't match return max( LCSLength(X, Y, Z, m - 1, n, o), LCSLength(X, Y, Z, m, n - 1, o), LCSLength(X, Y, Z, m, n, o - 1)); } // Longest Common Subsequence of K-sequences int main() { string X = "ABCBDAB", Y = "BDCABA", Z = "BADACB"; cout << "The length of LCS is " << LCSLength(X, Y, Z, X.length(), Y.length(), Z.length()); return 0; } |

`Output:`

The length of LCS is 4

The worst case time complexity of above solution is O(3^{(m+n+o)}). The worst case happens when there is no common subsequence present in X, Y, Z (i.e. LCS length is 0) and each recursive call will end up in three recursive calls.

The LCS problem exhibits overlapping subproblems. A problem is said to have overlapping subproblems if the recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are memoized rather than computed again and again. This method is illustrated below –

**Memoized C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <bits/stdc++.h> using namespace std; // Function to return maximum of three integers int max(int a, int b, int c) { return max(max(a, b), c); } // Function to find length of Longest Common Subsequence of // sequences X[0..m-1], Y[0..n-1] and Z[0..o-1] int LCSLength(string X, string Y, string Z, int m, int n, int o, auto &lookup) { // return if we have reached the end of either sequence if (m == 0 || n == 0 || o == 0) return 0; // construct a unique map key from dynamic elements of the input string key = to_string(m) + "|" + to_string(n) + "|" + to_string(o); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // if last character of X, Y, Z matches if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1]) lookup[key] = LCSLength(X, Y, Z, m - 1, n - 1, o - 1, lookup) + 1; else // else if last character of X, Y, Z don't match lookup[key] = max(LCSLength(X, Y, Z, m - 1, n, o, lookup), LCSLength(X, Y, Z, m, n - 1, o, lookup), LCSLength(X, Y, Z, m, n, o - 1, lookup)); } // return the subproblem solution from the map return lookup[key]; } // Longest Common Subsequence of K-sequences int main() { string X = "ABCBDAB", Y = "BDCABA", Z = "BADACB"; // create a map to store solutions of subproblems unordered_map<string, int> lookup; cout << "The length of LCS is " << LCSLength(X, Y, Z, X.length(), Y.length(), Z.length(), lookup); return 0; } |

`Output:`

The length of LCS is 4

The time complexity of above solution is O(mno) and auxiliary space used by the program is O(mno).

Above *Memo*ized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values. We can also solve this problem in bottom-up manner. In the bottom-up approach, we calculate the smaller values of LCS(i, j, k) first, then build larger values from them.

| 0 if i == 0 or j == 0 or k == 0

LCS[i][j][k] = | LCS[i-1][j-1][k-1] + 1 if X[i-1] == Y[j-1] == Z[k-1]

| longest(LCS[i-1][j][k], LCS[i][j-1][k], otherwise

LCS[i][j][k-1])

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <bits/stdc++.h> using namespace std; // Function to return maximum of three integers int max(int a, int b, int c) { return max(max(a, b), c); } // Function to find length of Longest Common Subsequence of // sequences X[0..m-1], Y[0..n-1] and Z[0..o-1] int LCSLength(string X, string Y, string Z) { int m = X.length(), n = Y.length(), o = Z.length(); // lookup table stores solution to already computed sub-problems // i.e. lookup[i][j][k] stores the length of LCS of substring // X[0..i-1], Y[0..j-1], Z[0..k-1] int lookup[m + 1][n + 1][o + 1]; // initalize lookup table with 0 memset(lookup, 0, sizeof lookup); // fill the lookup table in bottom-up manner for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= o; k++) { // if current character of X, Y and Z matches if (X[i - 1] == Y[j - 1] && Y[j - 1] == Z[k - 1]) lookup[i][j][k] = lookup[i - 1][j - 1][k - 1] + 1; // else if current character of X, Y and Z don't match else lookup[i][j][k] = max(lookup[i - 1][j][k], lookup[i][j - 1][k], lookup[i][j][k - 1]); } } } // LCS will be last entry in the lookup table return lookup[m][n][o]; } // Longest Common Subsequence of K-sequences int main() { string X = "ABCBDAB", Y = "BDCABA", Z = "BADACB"; cout << "The length of LCS is " << LCSLength(X, Y, Z); return 0; } |

`Output:`

The length of LCS is 4

The time complexity of above solution is O(mno) and auxiliary space used by the program is O(mno).

**References:** https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply