Java - Longest Common Subsequence (LCS)

Problem Statement

Given two strings X and Y, find the length of their longest common subsequence (LCS).

Example

Input:

X = "ABCBDAB";

Y = "BDCAB";

Output:

LCS length: 4

Explanation:

The longest common subsequence is "BCAB" (length = 4).

Approach

Dynamic Programming (Bottom-Up)

Create a DP table dp[i][j], where:

dp[i][j] stores LCS length of X[0...i-1] and Y[0...j-1].

Base Case:

If i == 0 or j == 0, dp[i][j] = 0 (empty string has no common subsequence).

Recurrence Relation:

If X[i-1] == Y[j-1]:

dp[i][j]=1+dp[i−1][j−1]

Else:

dp[i][j]=max(dp[i−1][j],dp[i][j−1])

Final Answer:

dp[m][n] gives the LCS length.

Java Code

import java.util.Scanner;

public class LCS {

    public static int longestCommonSubsequence(String X, String Y) {

        int m = X.length();

        int n = Y.length();

        int[][] dp = new int[m + 1][n + 1];

        // Filling DP table

        for (int i = 1; i <= m; i++) {

            for (int j = 1; j <= n; j++) {

                if (X.charAt(i - 1) == Y.charAt(j - 1)) {

                    dp[i][j] = 1 + dp[i - 1][j - 1]; // Matching character

                } else {

                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Max of skipping X[i] or Y[j]

                }

            }

        }

        return dp[m][n];

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);   

        System.out.print("Enter first string: ");

        String X = scanner.nextLine();      

        System.out.print("Enter second string: ");

        String Y = scanner.nextLine();    

        scanner.close();      

        System.out.println("LCS length: " + longestCommonSubsequence(X, Y));

    }

}