1. Introduction

The Longest Common Subsequence (LCS) problem is a classic computer science problem that deals with finding the longest sequence of characters that appear in the same order in both strings, not necessarily contiguous. For example, for strings “ABCBDAB” and “BDCAB”, the LCS is “BCAB”.

2. Program Steps

1. Initialize a two-dimensional array dp of size (m+1) x (n+1) where m and n are the lengths of the two input strings.

2. Fill the first row and first column with zeros.

3. Traverse through the strings and populate the dp array based on comparisons between characters of the two strings.

4. The value dp[i][j] will represent the length of LCS of the first i characters of string1 and first j characters of string2.

5. Return dp[m][n] as the length of the LCS for the complete strings.

3. Code Program

public class LongestCommonSubsequence {

    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCAB";
        int result = lcs(s1, s2);
        System.out.println("The length of the LCS is: " + result);
    }

    public static int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        // `dp` array where `dp[i][j]` will contain the length of LCS of s1[0..i-1] & s2[0..j-1]
        int[][] dp = new int[m+1][n+1];

        // Filling the dp array
        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]);
                }
            }
        }

        return dp[m][n];
    }
}
x

Output:

The length of the LCS is: 4

4. Step By Step Explanation

1. We utilize a dynamic programming approach to solve the LCS problem. The main idea is to use a dp table where each cell dp[i][j] represents the LCS length for the first i characters of string1 and the first j characters of string2.

2. The dp table is filled row-wise. When characters from the two strings match, we increment the value from the top-left diagonal cell. If they don't match, we take the maximum value from either directly above or directly to the left.

3. By the end of this process, the value in the bottom-right corner of the dp table (dp[m][n]) represents the length of the LCS for the complete strings.