Longest Common Subsequence - Java Solution

1. Introduction

In this blog post, we explore the "Longest Common Subsequence" problem, a fundamental challenge in the realm of dynamic programming and string processing. This problem involves finding the longest subsequence that is common to two given strings. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Problem

Given two strings text1 and text2, the task is to return the length of their longest common subsequence (LCS). If there is no common subsequence, the function should return 0.

Examples:

1. Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.

2. Input: text1 = "abc", text2 = "abc"

Output: 3

Explanation: The longest common subsequence is "abc" and its length is 3.

3. Input: text1 = "abc", text2 = "def"

Output: 0

Explanation: There is no common subsequence, so the result is 0.

2. Solution Steps

1. Use dynamic programming to build a 2D array dp where dp[i][j] represents the length of the longest common subsequence of text1[0...i] and text2[0...j].

2. Initialize the first row and column of dp to 0, as the LCS of an empty string and any string is 0.

3. Iterate through both strings and fill the dp array:

a. If characters at text1[i] and text2[j] are equal, dp[i][j] = dp[i-1][j-1] + 1.

b. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

4. The value at dp[text1.length()][text2.length()] gives the length of the LCS.

3. Code Program

public class LongestCommonSubsequence {
    public static void main(String[] args) {
        String text1 = "abcde", text2 = "ace";
        System.out.println(longestCommonSubsequence(text1, text2)); // Test the function
    }

    // Function to find the length of the longest common subsequence
    public static int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i - 1) == text2.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[text1.length()][text2.length()];
    }
}

Output:

3

Explanation:

1. longestCommonSubsequence: This function computes the length of the longest common subsequence between text1 and text2.

2. It initializes a 2D array dp where dp[i][j] represents the length of the LCS up to text1[i-1] and text2[j-1].

3. The function iterates through each character of text1 and text2, filling the dp array based on whether characters match and taking the maximum length found so far.

4. If characters match, it increments the count from the previous state; otherwise, it takes the maximum of the adjacent previous states.

5. The final value in dp[text1.length()][text2.length()] represents the length of the LCS.

6. This dynamic programming approach efficiently computes the LCS by building upon solutions to smaller subproblems.