Problem 2: Longest Common Subsequence

The longest common subsequence problem is a classic problem in computer science and is often used as an example to illustrate the use of dynamic programming.

In this problem, we are given two strings and we need to find the length of the longest subsequence that is common to both strings. A subsequence is a sequence of characters that appears in the same order in both strings, but not necessarily consecutively.

For example, consider the following strings:

1String s1 = "algorithm";
2String s2 = "rhythm";

The longest common subsequence between s1 and s2 is "rhm" with a length of 3.

To solve this problem using dynamic programming, we can use a 2D matrix to store the lengths of the longest common subsequences for different prefixes of the two strings. We can then fill in the matrix iteratively using the following rules:

• If the characters at the current positions are the same, we can extend the longest common subsequence by one and store this length in the matrix.
• If the characters at the current positions are different, we take the maximum of the length of the longest common subsequence obtained by considering one character less from each string.

Here's an example implementation in Java:

1public class LongestCommonSubsequence {
2
3    public static int longestCommonSubsequence(String s1, String s2) {
4        int m = s1.length();
5        int n = s2.length();
6
7        int[][] dp = new int[m+1][n+1];
8
9        for (int i = 1; i <= m; i++) {
10            for (int j = 1; j <= n; j++) {
11                if (s1.charAt(i-1) == s2.charAt(j-1)) {
12                    dp[i][j] = dp[i-1][j-1] + 1;
13                } else {
14                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
15                }
16            }
17        }
18
19        return dp[m][n];
20    }
21
22    public static void main(String[] args) {
23        String s1 = "algorithm";
24        String s2 = "rhythm";
25
26        int longestLength = longestCommonSubsequence(s1, s2);
27        System.out.println("The length of the longest common subsequence is: " + longestLength);
28    }
29}

In this code, we define a longestCommonSubsequence method that takes two strings s1 and s2 as input and returns the length of the longest common subsequence between them using dynamic programming.

We first initialize a 2D matrix dp to store the lengths of the longest common subsequences. The matrix has dimensions (m+1) x (n+1), where m and n are the lengths of s1 and s2, respectively.

We then iterate through the matrix and fill in the values using the rules mentioned earlier. Finally, we return the value at the bottom-right corner of the matrix, which represents the length of the longest common subsequence.

To test the code, we can call the longestCommonSubsequence method with two strings and print the result. For example, in the main method, we set s1 to "algorithm" and s2 to "rhythm", and print the length of the longest common subsequence between them.

Feel free to modify the code and test it with different strings to find the longest common subsequence!