Can you find the longest common subsequence of two strings using dynamic programming?

The Longest Common Subsequence (LCS) problem is a classic computer science problem often solved using dynamic programming. Given two sequences, this problem involves finding the longest subsequence present in both of them. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Here’s how you can find the longest common subsequence of two strings using dynamic programming:

Let’s denote the two input strings as ‘X[0..m-1]‘ and ‘Y[0..n-1]‘. For this process, we can start by initially defining a 2D matrix ‘dp[][]‘ of size ‘(m+1)x(n+1)‘.

Here, ‘dp[i][j]‘ will hold the length of the longest common subsequence of the prefixes ‘X[0..i-1]‘ and ‘Y[0..j-1]‘.

To clarify, here is the formula that will be used:
$$dp[i][j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ dp[i-1][j-1] + 1 & \text{if } X[i-1] = Y[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{if } X[i-1] \neq Y[j-1] \end{cases}$$
The approach behind this algorithm is as follows:

1. If ‘X[i-1]‘ is equal to ‘Y[j-1]‘, this means we have found a matching character in both strings. Thus, the LCS up to ‘i,j‘ is the LCS up to ‘i-1,j-1‘ extended by this matching character, hence we add 1 to ‘dp[i-1][j-1]‘.

2. If ‘X[i-1]‘ is not equal to ‘Y[j-1]‘, we have a choice to ignore either ‘X[i-1]‘ or ‘Y[j-1]‘. Select the previous cell that has the maximum LCS, i.e., maximum of ‘dp[i][j-1]‘ or ‘dp[i-1][j]‘.

The LCS of the complete strings ‘X‘ and ‘Y‘ is given by ‘dp[m][n]‘ which is the last cell.

For example, let ‘X = "ABCBDAB"` and ‘Y = "BDCAB"`. The LCS is ‘"BCAB"`. Following the above approach, here is what the filled table would look like:

       "" B D C A B
    "" 0  0 0 0 0 0 
    A  0  0 0 0 1 1
    B  0  1 1 1 1 2
    C  0  1 1 2 2 2
    B  0  1 1 2 2 3
    D  0  1 2 2 2 3
    A  0  1 2 2 3 3
    B  0  1 2 2 3 4

Every cell ‘dp[i][j]‘ holds the LCS length of the prefixes ‘X[0...i-1]‘ and ‘Y[0...j-1]‘, thus the LCS length for whole ‘X‘ and ‘Y‘ is ‘dp[m][n] = 4‘, which matches with our LCS string ‘"BCAB"` length. So, the bottom-right cell has the length of the LCS.

Bear in mind, this algorithm does not return the actual LCS, but only its length. To find the actual LCS string, one has to backtrack from the ‘dp[m][n]‘ cell according to the following rules: - If ‘X[i-1] = Y[j-1]‘, it means that this character is part of the LCS string, so add ‘X[i-1]‘ (or ‘Y[j-1]‘) to the LCS string and go diagonally up to ‘dp[i-1][j-1]‘. - If ‘X[i-1] != Y[j-1]‘, then go to the cell that contains the maximum value, which can be either ‘dp[i-1][j]‘ or ‘dp[i][j-1]‘. If both have the same value, either choice can work.

This backtrack approach will complete the LCS algorithm for finding not just the length, but also the LCS string.

Time complexity of this solution is ‘O(m*n)‘ (where m and n are string lengths) for the LCS length computing and ‘O(m+n)‘ for the LCS string recovering, so overall linear in terms of strings length.