Longest Common Subsequence: A Dynamic Programming Approach

1. What is a Longest Common Subsequence?

First, it's important to distinguish a subsequence from a substring.

• A substring must be a contiguous block of characters within a string. For "abcde", "bcd" is a substring, but "ace" is not.
• A subsequence is formed by deleting zero or more characters from a string while maintaining the relative order of the remaining characters. For "abcde", "ace" is a valid subsequence.

The Longest Common Subsequence (LCS) problem asks for the longest possible subsequence that is present in two given strings.

To see this in action, the following video provides a clear definition and example.

2. Devising a Strategy: Subproblems and Recurrence

Like other DP problems, LCS has an optimal substructure. The solution to the main problem can be built from solutions to smaller, overlapping subproblems. Let's think about this recursively.

Consider two strings, s1 and s2. We want to find LCS(s1, s2). Let's compare their last characters.

1. Case 1: The last characters match.
   If s1 ends with 'a' and s2 also ends with 'a', then this matching 'a' must be part of their LCS. Why? Including it gives us a common subsequence that is one character longer than what we could get from the strings without their last characters. So, the problem is reduced to finding the LCS of the prefixes (the strings without their last character) and appending 'a'.
   LCS(s1, s2) = LCS(s1_prefix, s2_prefix) + 'a'

2. Case 2: The last characters do not match.
   If s1 ends with 'a' and s2 ends with 'b', they can't both contribute to the end of the LCS. The LCS must therefore be the LCS of either (s1_prefix, s2) or (s1, s2_prefix), whichever is longer.
   LCS(s1, s2) = max(length(LCS(s1_prefix, s2)), length(LCS(s1, s2_prefix)))

This recursive logic generates many overlapping subproblems, as shown in the recursive tree for finding the LCS of "abcde" and "ace".

3. The Dynamic Programming Solution

To avoid re-computing subproblems, we use tabulation. We'll build a 2D table, dp, where dp[i][j] stores the length of the LCS for the prefixes s1[0...i-1] and s2[0...j-1].

• State: dp[i][j] = length of the LCS of s1's first i characters and s2's first j characters.
• Goal: The final answer will be dp[m][n], where m and n are the lengths of s1 and s2.
• Recurrence Relation: This directly follows our recursive logic:
  • If s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1] (We found a match, add 1 to the result from the smaller subproblem).
  • If s1[i-1] != s2[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (No match, so we carry forward the best result from the previous subproblems).
• Base Case: The dp table is initialized with zeros. dp[0][j] and dp[i][0] will be 0, as the LCS of any string and an empty string is 0.

The following video provides an excellent walkthrough of setting up and filling this DP table.

4. Implementation: Finding the Length

Here is a Python implementation that builds the dp table to find the length of the LCS. Notice how the code is a direct translation of the recurrence relation we just defined.

def lcs_length(s1, s2):
    m, n = len(s1), len(s2)
    
    # Create a DP table of size (m+1) x (n+1) and initialize with 0s.
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Iterate through the table to fill it bottom-up.
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # Case 1: Characters match
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            # Case 2: Characters do not match
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                
    # The bottom-right cell contains the length of the LCS.
    # We return the whole table because we'll need it for backtracking.
    return dp

# Example
s1 = "AGGTAB"
s2 = "GXTXAYB"
dp_table = lcs_length(s1, s2)
lcs_len = dp_table[len(s1)][len(s2)]
print(f"The length of the LCS is: {lcs_len}") # Output: 4

5. Reconstructing the LCS String

The DP table gives us the length, but what if we want the actual subsequence? For this, we backtrack through the filled DP table, starting from the bottom-right corner.

The following article explains the traceback logic clearly.

Here's the Python code for the backtracking function. It takes the filled DP table and the original strings as input.

def backtrack_lcs(dp_table, s1, s2):
    lcs = ""
    i, j = len(s1), len(s2)
    
    while i > 0 and j > 0:
        # If characters match, this character is part of the LCS.
        if s1[i - 1] == s2[j - 1]:
            lcs = s1[i - 1] + lcs  # Prepend the character
            i -= 1
            j -= 1
        # If not, move to the cell that gave the max value.
        elif dp_table[i - 1][j] > dp_table[i][j - 1]:
            i -= 1  # Move up
        else:
            j -= 1  # Move left
            
    return lcs

# Continuing our example:
s1 = "AGGTAB"
s2 = "GXTXAYB"
# dp_table is already computed from the previous step

result_lcs = backtrack_lcs(dp_table, s1, s2)
print(f"The LCS is: '{result_lcs}'") # Output: 'GTAB'

Conclusion

Congratulations on completing the Dynamic Programming module! The LCS problem is a powerful demonstration of 2D DP, reinforcing the concepts of optimal substructure and overlapping subproblems that you first saw with the Knapsack problem.

Key Takeaways:

• The LCS problem seeks the longest subsequence common to two strings, where elements maintain relative order but need not be contiguous.
• The 2D DP state dp[i][j] effectively stores the solution for prefixes of the strings.
• The recurrence relation is based on two simple cases: whether the characters at the current positions match or not.
• Finding the length of the LCS has a time and space complexity of O(m * n), where m and n are the string lengths.
• The actual subsequence can be reconstructed by backtracking through the filled DP table from the end.

Up Next:
The backtracking we did today to find the LCS string was a specific application of a broader, powerful algorithmic paradigm. In the next module, Backtracking, we will formalize this technique. You will learn the general "choose, explore, un-choose" template that can be used to solve an entirely new class of problems, such as generating all permutations or combinations of a set, and solving classic puzzles like N-Queens and Sudoku.