Question

How to find the length of the longest common subsequence (LCS) in two strings with Java

Answer 1

public class Program {

    // Compute the Longest Common Subsequence (LCS) length using recursion
    public static int lcs(char[] s1, char[] s2, int s1_len, int s2_len) {

        // Base case: if either string is empty, LCS length is 0
        if (s1_len == 0 || s2_len == 0)
            return 0;

        // If last characters match, include this character in LCS
        if (s1[s1_len - 1] == s2[s2_len - 1])
            return 1 + lcs(s1, s2, s1_len - 1, s2_len - 1);

        // Otherwise, take the maximum LCS by:
        // 1. Removing last char of s2
        // 2. Removing last char of s1
        return mymax(
            lcs(s1, s2, s1_len, s2_len - 1),
            lcs(s1, s2, s1_len - 1, s2_len)
        );
    }

    // Simple helper to return the larger of two integers
    public static int mymax(int a, int b) {
        return (a > b) ? a : b;
    }

    public static void main(String[] args) {

        // Input strings
        String s1 = "accyrb";
        String s2 = "cyxyazb";

        // Convert to char arrays for recursive processing
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();

        // Compute and print the LCS length
        System.out.println("The length of LCS is: " +
            lcs(cs1, cs2, cs1.length, cs2.length));
    }
}

     
/*
run:
    
The length of LCS is: 3
     
*/

 

70+ SQL courses for beginners and professionals

Answer 2

/**
    This program computes BOTH:
      1. The length of the Longest Common Subsequence (LCS)
      2. The actual LCS subsequence

    It uses an efficient dynamic‑programming algorithm:
        Time:  O(n * m)
        Space: O(n * m)

    dp[i][j] stores the LCS length between:
        s1[0..i-1] and s2[0..j-1]

    Recurrence:
        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])

    After filling the DP table, we reconstruct the LCS by
    walking backwards from dp[n][m].
*/

public class LCS {

    // Function that returns both LCS length and the subsequence
    public static Result lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        // DP table
        int[][] dp = new int[n + 1][m + 1];

        // Fill DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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]);
                }
            }
        }

        // Reconstruct the LCS sequence
        int index = dp[n][m];
        char[] lcsChars = new char[index];

        int i = n, j = m;

        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                // Character is part of LCS
                lcsChars[index - 1] = s1.charAt(i - 1);
                index--;
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--; // Move up
            } else {
                j--; // Move left
            }
        }

        return new Result(dp[n][m], new String(lcsChars));
    }

    // Helper class to return both length and sequence
    static class Result {
        int length;
        String sequence;

        Result(int length, String sequence) {
            this.length = length;
            this.sequence = sequence;
        }
    }

    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        Result result = lcs(s1, s2);

        System.out.println("String 1: " + s1);
        System.out.println("String 2: " + s2);
        System.out.println("Length of LCS: " + result.length);
        System.out.println("LCS sequence: " + result.sequence);
    }
}


/*
run:

String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB

*/

 

70+ SQL courses for beginners and professionals