Java Program to Find Longest Common Subsequence

You can find the longest common subsequence in Java by using dynamic programming with a 2D array to store lengths and then reconstructing the subsequence; for example, use int[][] dp = new int[m+1][n+1] to build the solution and backtrack to get the subsequence.

Examples

InputString s1 = "ABCBDAB", String s2 = "BDCABA"

OutputLongest Common Subsequence: BCBA

InputString s1 = "AGGTAB", String s2 = "GXTXAYB"

OutputLongest Common Subsequence: GTAB

InputString s1 = "", String s2 = "ABC"

OutputLongest Common Subsequence:

How to Think About It

To find the longest common subsequence, compare characters of both strings one by one. If characters match, include that character and move diagonally in the comparison table. If not, take the longer subsequence from either ignoring the current character of the first string or the second string. Use a table to store results of smaller problems to avoid repeated work.

Algorithm

1

Create a 2D array dp with size (length of s1 + 1) x (length of s2 + 1) initialized to 0

2

Fill dp by comparing characters of s1 and s2: if characters match, dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3

Start from dp[m][n] and backtrack to find the subsequence by moving diagonally if characters match or moving in the direction of the larger dp value

4

Build the subsequence string in reverse during backtracking

5

Return the reversed subsequence string as the longest common subsequence

Code

java

public class LCS {
    public static String longestCommonSubsequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                sb.append(s1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCABA";
        System.out.println("Longest Common Subsequence: " + longestCommonSubsequence(s1, s2));
    }
}

Output

Longest Common Subsequence: BCBA

Dry Run

Let's trace the example s1 = "ABCBDAB" and s2 = "BDCABA" through the code

1

Initialize dp array

Create a 8x7 dp array filled with zeros (since s1 length=7, s2 length=6)

2

Fill dp table

Compare characters and fill dp: for example, dp[1][1] compares 'A' and 'B' (no match, max of dp[0][1], dp[1][0] = 0), dp[2][2] compares 'B' and 'D' (no match), dp[2][1] compares 'B' and 'B' (match, dp[1][0]+1=1), etc.

3

Backtrack to find subsequence

Start at dp[7][6], move diagonally when characters match, else move to the larger dp neighbor, collecting characters 'B', 'C', 'B', 'A' in reverse order.

4

Build result

Reverse collected characters to get 'BCBA' as the longest common subsequence.

i	j	s1.charAt(i-1)	s2.charAt(j-1)	dp[i][j]
1	1	A	B	0
2	1	B	B	1
3	2	C	D	1
4	3	B	C	1
5	4	D	A	2
6	5	A	B	3
7	6	B	A	3

Why This Works

Step 1: Building the dp table

The dp table stores lengths of longest common subsequences for substrings of s1 and s2, allowing reuse of previous results.

Step 2: Filling dp with matches and max values

If characters match, increase length by 1 from the diagonal cell; otherwise, take the maximum from left or top cell to keep the longest subsequence length.

Step 3: Backtracking to find subsequence

Starting from the bottom-right, move diagonally when characters match to collect subsequence characters; otherwise, move towards the cell with the larger dp value.

Alternative Approaches

Recursive with memoization

java

public class LCSRecursive {
    public static int lcsLength(String s1, String s2, int i, int j, int[][] memo) {
        if (i == s1.length() || j == s2.length()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = 1 + lcsLength(s1, s2, i + 1, j + 1, memo);
        } else {
            memo[i][j] = Math.max(lcsLength(s1, s2, i + 1, j, memo), lcsLength(s1, s2, i, j + 1, memo));
        }
        return memo[i][j];
    }

    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCABA";
        int[][] memo = new int[s1.length()][s2.length()];
        for (int[] row : memo) java.util.Arrays.fill(row, -1);
        System.out.println("Length of LCS: " + lcsLength(s1, s2, 0, 0, memo));
    }
}

This approach calculates length only and uses recursion with memoization, which is easier to write but less efficient for large inputs.

Bottom-up dp with space optimization

java

public class LCSSpaceOpt {
    public static int lcsLength(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[] prev = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            int[] curr = new int[n + 1];
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            prev = curr;
        }
        return prev[n];
    }

    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCABA";
        System.out.println("Length of LCS: " + lcsLength(s1, s2));
    }
}

This method uses less memory by storing only one row at a time but does not reconstruct the subsequence.

Complexity: O(m*n) time, O(m*n) space

Time Complexity

The algorithm uses two nested loops over the lengths of the two strings, resulting in O(m*n) time.

Space Complexity

It uses a 2D array of size (m+1)*(n+1) to store intermediate results, so space is O(m*n).

Which Approach is Fastest?

The bottom-up dp approach is fastest for large inputs; recursive memoization is simpler but slower; space-optimized dp saves memory but can't reconstruct subsequence.

Approach	Time	Space	Best For
Bottom-up DP with reconstruction	O(m*n)	O(m*n)	Finding subsequence and length
Recursive with memoization	O(m*n)	O(m*n)	Simple code for length only
Space-optimized DP	O(m*n)	O(n)	Memory saving for length only