# 1. Introduction

The "Longest Common Subsequence" problem is a fundamental challenge in computer science, often encountered in the field of dynamic programming. It involves finding the longest subsequence common to two strings, which is a sequence that appears in both strings in the same order, but not necessarily consecutively. This problem is a classic in algorithm design, particularly in text processing and bioinformatics.

## Problem

Given two strings *text1* and *text2*, the task is to return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters deleted (possibly none) without changing the order of the remaining characters. If there is no common subsequence, return 0.

# 2. Solution Steps

1. Initialize a 2D array *dp* with dimensions *(len(text1) + 1) x (len(text2) + 1)* to store the lengths of common subsequences.

2. Set all elements in *dp* to 0.

3. Iterate through each character of *text1* and *text2*.

4. Update *dp[i][j]* as *dp[i-1][j-1] + 1* if characters at *text1[i-1]* and *text2[j-1]* match.

5. If characters do not match, set *dp[i][j]* to the maximum of *dp[i-1][j]* and *dp[i][j-1]*.

6. The value at *dp[len(text1)][len(text2)]* gives the length of the longest common subsequence.

# 3. Code Program

```
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# Example Usage
print(longestCommonSubsequence("abcde", "ace"))
print(longestCommonSubsequence("abc", "abc"))
print(longestCommonSubsequence("abc", "def"))
```

### Output:

3 3 0

### Explanation:

**1. Dynamic Programming Table**: The 2D array *dp* is used to store the length of the longest common subsequence at each point.

**2. Table Initialization**: The table is initialized with zeros, representing no common subsequence.

**3. Iterative Comparison**: The strings *text1* and *text2* are compared character by character.

**4. Subsequence Length Calculation**: When characters match, the subsequence length is incremented; otherwise, the maximum length from previous steps is carried forward.

**5. Result Determination**: The value at *dp[len(text1)][len(text2)]* is the length of the longest common subsequence of *text1* and *text2*.

**6. Comprehensive Solution**: This approach efficiently calculates the longest common subsequence using dynamic programming.

## Comments

## Post a Comment