Longest Common Subsequence: Problem and Reconstruction

1. What is a Longest Common Subsequence?

First, let's clarify our terms. Given a sequence (like a string), a subsequence is formed by deleting zero or more characters from the original sequence, while keeping the remaining characters in their original relative order. This is different from a substring, which must be a contiguous block of characters.

For example, for the string ABCDEFG:

• ACEG is a subsequence.
• CD is a subsequence and a substring.
• AGF is not a subsequence, because the F and G are out of order.

The Longest Common Subsequence (LCS) problem takes two sequences, X and Y, and asks for the longest subsequence that is common to both.

For example, if X = "ABCBDAB" and Y = "BDCABA", the longest common subsequence is BCBA, which has a length of 4. Note that BCAB is another valid LCS of the same length. The solution isn't always unique, but its length is.

2. Formulating the DP Solution

Just like with the Knapsack problem, the key is to define a subproblem that has an optimal substructure. Since we are dealing with two input sequences, our subproblems will need to incorporate information about both.

A powerful way to think about this is to define subproblems on suffixes of the original strings. Let's say our strings are A and B. We can define a function L(i, j) that gives the length of the LCS for the suffixes A[i:] (from index i to the end) and B[j:] (from index j to the end).

To find L(i, j), we look at the first characters of our current suffixes, A[i] and B[j]:

1. If A[i] == B[j]: The characters match! This character can be part of our LCS. The length of the LCS will be 1 (for this character) plus the length of the LCS of the rest of the suffixes. So, we have 1 + L(i+1, j+1).

2. If A[i] != B[j]: The characters don't match. This means we cannot include both A[i] and B[j] at the start of our common subsequence. We have to discard one of them.

   • If we discard A[i], the problem becomes finding the LCS of A[i+1:] and B[j:], which is L(i+1, j).
   • If we discard B[j], the problem becomes finding the LCS of A[i:] and B[j+1:], which is L(i, j+1).
     Since we want the longest common subsequence, we take the maximum of these two possibilities.

This gives us the complete recurrence relation:

The base cases occur when either i or j goes past the end of the string, meaning we've reached an empty suffix. The LCS of anything and an empty string is 0.

3. The Tabulation Approach

While the suffix-based recurrence is great for theoretical understanding, most practical implementations use a prefix-based approach. It's slightly more intuitive when filling a table from the top-left.

Let's define dp[i][j] as the length of the LCS of the prefixes A[0...i-1] and B[0...j-1]. The table will have len(A)+1 rows and len(B)+1 columns to account for empty prefixes.

The recurrence is very similar, just with indices decreasing instead of increasing:

• If A[i-1] == B[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
• If A[i-1] != B[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

We fill the table starting from dp[0][0], and the final answer (the length of the LCS for the entire strings) will be in the bottom-right cell, dp[len(A)][len(B)].

For reference, here is the pseudocode that implements this logic. Notice how it mirrors the structure of the Knapsack tabulation algorithm, with two nested loops filling a 2D array.

4. Reconstructing the Subsequence

Just like with Knapsack, our DP table holds the key to finding not just the length, but the actual subsequence. We can reconstruct it by backtracking from the bottom-right cell (dp[len(A)][len(B)]).

Here is the logic for backtracking from cell (i, j):

1. Compare the characters A[i-1] and B[j-1].
2. If they are equal, this character is part of the LCS. We prepend it to our result and move diagonally to cell (i-1, j-1).
3. If they are not equal, we didn't find a match. We need to figure out which direction contributed to the maximum value in the current cell. We move to the larger of the two adjacent cells:
   • If dp[i-1][j] > dp[i][j-1], we move up to (i-1, j).
   • Otherwise, we move left to (i, j-1). (If they're equal, either path works, leading to potentially different but equally long LCSs).
4. We repeat this process until we reach the first row or column of the table.

To see this as an algorithm, you can again refer to the Wikipedia resource.

5. Complexity Analysis

Let the lengths of the two strings be m and n.

• Time Complexity: The algorithm is dominated by filling the DP table. Since we have a nested loop structure that iterates through each cell of the (m+1) x (n+1) table once, and each computation is constant time, the overall time complexity is $O(m\cdot n)$.
• Space Complexity: We need to store the entire (m+1) x (n+1) table to perform the backtracking. Therefore, the space complexity is $O(m\cdot n)$.

As with the Knapsack problem, it is possible to optimize the space to $O(\min (m,n))$ if you only need the length of the LCS. However, this optimization makes reconstructing the actual subsequence more complex, so the $O(m\cdot n)$ space approach is standard when the subsequence itself is required.

Conclusion

Great work! You have now solved another classic DP problem. The Longest Common Subsequence problem demonstrates how dynamic programming can be applied to problems involving sequences by defining subproblems based on their prefixes or suffixes.

Key Takeaways:

• The LCS problem seeks the longest ordered sequence of characters common to two strings.
• The DP subproblem can be defined on prefixes (or suffixes) of the input strings: dp[i][j] = LCS of A[0...i-1] and B[0...j-1].
• The recurrence relation depends on whether the characters at the current positions match or not.
• A 2D table of size $O(m\cdot n)$ is filled to find the length of the LCS.
• The actual subsequence is found by backtracking from the end of the table, following the decisions made at each step.

Preview of the Next Lesson:
We will continue exploring DP on sequences by looking at the Longest Increasing Subsequence (LIS) problem. While it also deals with subsequences, it only involves a single input sequence and requires a cleverer subproblem definition than what we've seen so far. It will be a great test of your growing DP skills