Longest Common Subsequence - Python Solution

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.