Longest Common Subsequence

XXX. Longest Common Subsequence

Dynamic Programming

String

Problem Statement:

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Algorithm:

The solution uses dynamic programming:

1. Create a DP table dp of size (text1.length + 1) x (text2.length + 1) to store the lengths of longest common subsequences for substrings of text1 and text2.
2. Iterate through both strings, comparing characters:
• If the characters match, update dp[i][j] to dp[i-1][j-1] + 1.
• If they do not match, update dp[i][j] to max(dp[i-1][j], dp[i][j-1]).
3. The value at dp[text1.length][text2.length] will be the length of the longest common subsequence.

Complexity:

Time Complexity: O(m * n), where m is the length of text1 and n is the length of text2. Each cell in the DP table is filled once.
Space Complexity: O(m * n), for the DP table.

Java Implementation:

public class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // Create a DP table with extra row and column for base cases
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        // Fill the DP table
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                // If characters match, take the diagonal value and add 1
                if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    // Else, take the maximum of the cell above or to the left
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        // Return the value in the bottom-right corner of the table
        return dp[text1.length()][text2.length()];
    }
}