How to Solve the Longest Common Subsequence Problem

Introduction

The Longest Common Subsequence (LCS) problem is a classic computer science problem used in fields like bioinformatics, file comparison, and version control systems. It involves finding the longest sequence of characters that appear left-to-right (but not necessarily contiguously) in both input strings.

For example, given the strings "ACDBE" and "ABCDE", the LCS is "ACDE".

Problem Definition

The problem is about finding the length (optionally, the content) of the longest subsequence present in both of two sequences. That is a sequence that appears in the same relative order, but not necessarily contiguously.

This is different from substrings, which require characters to be continuous.

Dynamic Programming Approach

The LCS problem can be efficiently solved using dynamic programming. We use a 2D array to store solutions to subproblems. The idea is to build a table where each cell (i, j) contains the length of the LCS of the first i characters of one string and the first j characters of the other string.

If characters at position i-1 and j-1 are equal, then
dp[i][j] = dp[i-1][j-1] + 1
Otherwise,
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Java Implementation

Here’s a Java program that calculates the LCS length and also reconstructs the LCS string.

public class LCSProblem {

    public static String longestCommonSubseq(String input1, String input2) {
        int m = input1.length();
        int n = input2.length();
        int[][] dbArr = new int[m + 1][n + 1];

        // Build the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (input1.charAt(i - 1) == input2.charAt(j - 1)) {
                    dbArr[i][j] = dbArr[i - 1][j - 1] + 1;
                } else {
                    dbArr[i][j] = Math.max(dbArr[i - 1][j], dbArr[i][j - 1]);
                }
            }
        }

        // Reconstruct the LCS from the DP table
        StringBuilder lcsString = new StringBuilder();
        int i = m, j = n;

        while (i > 0 && j > 0) {
            if (input1.charAt(i - 1) == input2.charAt(j - 1)) {
                lcsString.append(input1.charAt(i - 1));
                i--;
                j--;
            } else if (dbArr[i - 1][j] > dbArr[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        return lcsString.reverse().toString();
    }

    public static void main(String[] args) {
        String s1 = "ACDBE";
        String s2 = "ABCDE";
        String result = longestCommonSubseq(s1, s2);
        System.out.println("LCS: " + result);
    }
}

Output

For the input strings "ACDBE" and "ABCDE", the program will output:

makefileCopiaModificaLCS: ACDE

Time and Space Complexity

Time Complexity: O(m * n), where m and n are lengths of the two strings.
Space Complexity: O(m * n) due to the 2D array used for memoization.

If only the length of the LCS is required, and not the sequence itself, the space complexity can be optimized to O(min(m, n)).

Conclusion

The Longest Common Subsequence problem is a foundational problem in computer science that demonstrates the power of dynamic programming. It’s applicable in real-world tasks such as diff tools, merging changes in version control, and DNA sequence analysis. With efficient implementations, LCS can be used in systems requiring performance and accuracy.

You can find the example code on Github.