# 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.

## Comments

## Post a Comment