Longest Common Subsequence: Length and Reconstruction

1. What is a Longest Common Subsequence?

First, let's be clear on the terminology. A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements. This is different from a substring, which must be a contiguous block of characters.

For example, for the string "abcde":

• "ace" is a subsequence.
• "abd" is a subsequence.
• "bce" is a subsequence.
• "bcd" is a substring and a subsequence.
• "aec" is not a subsequence because the order of 'a' and 'e' is changed relative to 'c'.

A common subsequence is a subsequence that is present in two different strings. The Longest Common Subsequence (LCS) is the common subsequence with the greatest possible length.

Let's watch a short video to see this explained with clear examples.

A brute-force approach would involve generating all subsequences of one string (which is an exponential number, $O(2^N)$) and checking if they are present in the second string. This is highly inefficient. As you might guess, Dynamic Programming offers a much better way.

2. Finding the Length of the LCS

Let's develop the DP solution, starting with the recurrence relation. This logic is the heart of the problem.

Imagine we have two strings, s1 and s2, of lengths n and m respectively. We want to find the LCS of these two strings. We can define a function, lcs(i, j), that returns the length of the LCS for the prefixes s1[0...i] and s2[0...j].

Now, consider the last characters of these prefixes, s1[i] and s2[j]:

1. If the characters match (s1[i] == s2[j]):
   Great! This matching character is part of our LCS. We can add 1 to our count and then solve the smaller subproblem for the strings without these last characters.
   The length is 1 + lcs(i-1, j-1).

2. If the characters do not match (s1[i] != s2[j]):
   We cannot use this pair of characters. Our LCS must be formed from a smaller set of characters. We have two choices:

   • Either the LCS is the same as the LCS of s1[0...i-1] and s2[0...j] (we discard s1[i]).
   • Or it's the same as the LCS of s1[0...i] and s2[0...j-1] (we discard s2[j]).
     Since we want the longest common subsequence, we take the maximum of these two possibilities.
     The length is max(lcs(i-1, j), lcs(i, j-1)).

This recurrence relation has overlapping subproblems, making it a perfect candidate for DP. The following video walks through this derivation in detail and shows how to convert it into both a memoized (top-down) and tabulated (bottom-up) solution.

Tabulation Implementation

As the video explained, the tabulated approach is often preferred for its efficiency (no recursion overhead). We create a 2D array, dp[n+1][m+1], where dp[i][j] will store the length of the LCS of s1.substring(0, i) and s2.substring(0, j).

Here is a clean Java implementation of the tabulation logic.

The final answer, the length of the LCS for the full strings, will be in the bottom-right cell, dp[n][m].

3. Reconstructing the LCS

Just like with the 0/1 Knapsack, our DP table holds the value of the optimal solution (the length), but not the solution itself (the string). To get the actual string, we must backtrack through the table.

The process is intuitive and directly follows the logic we used to build the table:

1. Start at the bottom-right corner of the table: i = n, j = m.
2. While i > 0 and j > 0:
   • If s1.charAt(i-1) == s2.charAt(j-1):
     This means the characters match and are part of the LCS. We add this character to our result and move diagonally up and to the left (i--, j--).
   • Else (if they don't match):
     We must have arrived at dp[i][j] from the cell with the larger value. If dp[i-1][j] > dp[i][j-1], it means we came from above, so we move up (i--). Otherwise, we came from the left, so we move left (j--).
3. Since we built the string from end to beginning, we need to reverse it to get the final LCS.

Let's look at a visual of this process.

The following video provides a walkthrough of this reconstruction logic.

Reconstruction Implementation

Now, let's look at the complete Java code that combines filling the table and then backtracking to print the result.

Conclusion

Well done! You have now learned how to solve one of the most fundamental dynamic programming problems. The patterns you've used today—defining a recurrence based on choices, building a 2D table, and backtracking to find the solution—are incredibly powerful and versatile.

Key Takeaways:

• The LCS problem can be solved efficiently using a 2D DP table where dp[i][j] stores the LCS length of the first i characters of s1 and the first j characters of s2.
• The recurrence relation depends on a simple choice: if the last characters match, we take them and solve for the smaller prefix; if not, we take the best of two smaller subproblems.
• Time Complexity: $O(n\times m)$ to fill the DP table.
• Space Complexity: $O(n\times m)$ to store the table. The reconstruction adds $O(n+m)$ time but no significant extra space.
• The final LCS string is found by backtracking through the filled DP table from the bottom-right corner.

Preview of the Next Lesson:
We will continue our exploration of DP with another important subsequence problem: the Longest Increasing Subsequence (LIS). While it sounds similar, the LIS problem requires a different way of defining the DP state and opens the door to a very clever optimization that reduces the time complexity from $O(n^2)$ to $O(n\log n)$.