Problem Statement

The Longest Common Subsequence (LCS) problem is about finding the longest subsequence that is common to two sequences. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously.

Approach Explanation

The LCS problem can be solved using dynamic programming. The idea is to build a table that stores the lengths of the longest common subsequence for different pairs of prefixes of the two strings.

Dynamic Programming Structure:

1. Define a 2D DP table where dp[i][j] represents the length of the LCS of the first i characters of string A and the first j characters of string B.
2. Initialize the first row and first column of the table with zeros, as the LCS of any string with an empty string is 0.
3. Iterate through both strings. If the characters match, increment the value from the top-left diagonal by 1. If they do not match, take the maximum value from the left and top cells.
4. The final answer will be found in dp[m][n], where m and n are the lengths of the two strings.

Time Complexity:

O(m * n), where m and n are the lengths of the two strings.

Space Complexity:

O(m * n) for the DP table.

Python Code

def longest_common_subsequence(A, B):
    """
    Function to find the length of the longest common subsequence
    of two strings.

    Args:
    A (str): First input string.
    B (str): Second input string.

    Returns:
    int: Length of the longest common subsequence.
    """
    m, n = len(A), len(B)
    
    # Create a 2D DP table initialized to 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[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
string1 = "AGGTAB"
string2 = "GXTXAYB"
length = longest_common_subsequence(string1, string2)

print("Length of Longest Common Subsequence is:", length)
    

Explanation of the Program

Let’s break down the structure of the program:

1. Input:

The input consists of two strings for which we want to find the longest common subsequence. For example:

    string1 = "AGGTAB"
    string2 = "GXTXAYB"

2. DP Table Initialization:

A DP table is created with dimensions (m + 1) x (n + 1), initialized to zeros. This table is used to store the lengths of LCS for different substrings.

3. Iteration Over the Strings:

The program iterates over each character of both strings. If the characters at the current indices match, the value in the DP table is updated to be one more than the value diagonally up-left. If they do not match, the value is set to the maximum of the values from the left and top cells.

4. Final Result:

The length of the longest common subsequence can be found in the bottom-right cell of the DP table: dp[m][n].

Example Execution:

For the provided input strings, the output will display the length of the longest common subsequence:

Length of Longest Common Subsequence is: 4

This indicates that the longest common subsequence between “AGGTAB” and “GXTXAYB” has a length of 4, which corresponds to the subsequence “GTAB”.