Problem

Given three sequences A = $(a_1, a_2, \ldots, a_n)$ , B = $(b_1, b_2, \ldots, b_m)$, and C = $(c_1, c_2, \ldots, c_l)$, find the length of their longest common subsequence.

Examples

Example 1:

1
2

Input: a = [1, 2, 3], b = [2, 1, 3], c = [1, 3, 5]
Output: [1, 3]

Solution

Method 1 - DP

To solve this problem, we will use a dynamic programming approach similar to the classic longest common subsequence problem, but extended to three sequences.

Steps

  1. Define a 3D DP Table:
    • Let dp[i][j][k] represent the length of the longest common subsequence of the first i elements of ( a ), the first j elements of ( b ), and the first k elements of ( c ).
  2. Initialize the DP Table:
    • Initialize dp[0][x][y] = 0, dp[x][0][y] = 0, and dp[x][y][0] = 0 for all valid x and y.
  3. Fill the DP Table:
    • Iterate through all elements of ( a ), ( b ), and ( c ). For each i, j, and k:
      • If a[i-1], b[j-1], and c[k-1] are equal, then dp[i][j][k] = dp[i-1][j-1][k-1] + 1.
      • Otherwise, take the maximum of excluding one element from either a, b, or c.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int longestCommonSubsequence3(int[] a, int[] b, int[] c) {
        int n = a.length;
        int m = b.length;
        int l = c.length;
        
        int[][][] dp = new int[n + 1][m + 1][l + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 1; k <= l; k++) {
                    if (a[i - 1] == b[j - 1] && a[i - 1] == c[k - 1]) {
                        dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                    } else {
                        dp[i][j][k] = Math.max(Math.max(dp[i - 1][j][k], dp[i][j - 1][k]), dp[i][j][k - 1]);
                    }
                }
            }
        }
        
        return dp[n][m][l];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def longest_common_subsequence3(self, a: List[int], b: List[int], c: List[int]) -> int:
        n, m, l = len(a), len(b), len(c)
        
        # Initialize the DP table
        dp = [[[0] * (l + 1) for _ in range(m + 1)] for _ in range(n + 1)]
        
        # Fill the DP table
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                for k in range(1, l + 1):
                    if a[i - 1] == b[j - 1] == c[k - 1]:
                        dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
                    else:
                        dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
        
        return dp[n][m][l]

Complexity

  • ⏰ Time complexity: O(n * m * l), where n, m, and l are the lengths of the sequences ( a ), ( b ), and ( c ) respectively. This is because we fill a 3D DP table.
  • 🧺 Space complexity: O(n * m * l), due to storing the DP table.