Python - LCS of Three Strings

Python – LCS of Three Strings

The Longest Common Subsequence (LCS) problem is a classic dynamic programming challenge. In this tutorial, we focus on finding the LCS among three strings. The goal is to determine the longest sequence that appears in all three strings (the characters need not be contiguous, but their order must be preserved).

Problem Statement

Given three strings s1, s2, and s3, your task is to find the longest common subsequence (LCS) present in all three strings. The subsequence should maintain the relative order of characters from the original strings.

Sample Input and Output

Example 1:

</>

Copy

# Input:
s1 = "abcd1e2"
s2 = "bcd12ea"
s3 = "bd1ea"

# Expected Output:
# The LCS is "bd1e" and its length is 4.

Explanation: In this example, the common subsequence “bd1e” is found in all three strings while preserving the order of characters. Even though the strings contain extra characters, “bd1e” is the longest sequence that appears in every string.

Example 2:

</>

Copy

# Input:
s1 = "tutorial"
s2 = "tutorialkart"
s3 = "tutorialkart.com"

# Expected Output:
# The LCS is "tutorial" and its length is 8.

Explanation: Although the second and third strings have additional characters, the sequence “geeks” is present in all three inputs and is the longest subsequence common to them.

Solution Approach

To solve the LCS problem for three strings using dynamic programming, we build a 3-dimensional DP table dp[i][j][k] where each cell represents the length of the LCS for the substrings s1[0...i-1], s2[0...j-1], and s3[0...k-1]. The recurrence relations are:

If s1[i-1] == s2[j-1] == s3[k-1]:

dp[i][j][k] = dp[i-1][j-1][k-1] + 1

Otherwise:

dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])

The base case is when any of the indices i, j, or k is 0, in which case the LCS length is 0.

Python Program

</>

Copy

def lcs_of_three(s1, s2, s3):
    """
    Compute the length of the Longest Common Subsequence (LCS) for three strings using Dynamic Programming.
    
    Parameters:
    s1, s2, s3 (str): The input strings.
    
    Returns:
    int: The length of the LCS.
    str: One of the possible LCS (constructed via backtracking).
    """
    n1, n2, n3 = len(s1), len(s2), len(s3)
    
    # Initialize a 3D DP table with dimensions (n1+1) x (n2+1) x (n3+1)
    dp = [[[0]*(n3+1) for _ in range(n2+1)] for __ in range(n1+1)]
    
    # Build the DP table
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            for k in range(1, n3+1):
                if s1[i-1] == s2[j-1] == s3[k-1]:
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1
                else:
                    dp[i][j][k] = max(
                        dp[i-1][j][k],
                        dp[i][j-1][k],
                        dp[i][j][k-1]
                    )
    
    # Reconstruct one LCS by backtracking through the DP table
    i, j, k = n1, n2, n3
    lcs = []
    while i > 0 and j > 0 and k > 0:
        if s1[i-1] == s2[j-1] == s3[k-1]:
            lcs.append(s1[i-1])
            i -= 1
            j -= 1
            k -= 1
        else:
            # Choose the direction with the highest value
            if dp[i-1][j][k] >= dp[i][j-1][k] and dp[i-1][j][k] >= dp[i][j][k-1]:
                i -= 1
            elif dp[i][j-1][k] >= dp[i-1][j][k] and dp[i][j-1][k] >= dp[i][j][k-1]:
                j -= 1
            else:
                k -= 1
    lcs.reverse()
    lcs_str = "".join(lcs)
    
    return dp[n1][n2][n3], lcs_str

# Test Example 1
s1 = "abcd1e2"
s2 = "bcd12ea"
s3 = "bd1ea"
length, lcs_string = lcs_of_three(s1, s2, s3)
print("Example 1:")
print("Input Strings:", s1, s2, s3)
print("Length of LCS:", length)    # Expected: 4
print("LCS:", lcs_string)          # Expected LCS: "bd1e"

# Test Example 2
s1 = "tutorial"
s2 = "tutorialkart"
s3 = "tutorialkart.com"
length, lcs_string = lcs_of_three(s1, s2, s3)
print("\nExample 2:")
print("Input Strings:", s1, s2, s3)
print("Length of LCS:", length)    # Expected: 8
print("LCS:", lcs_string)          # Expected LCS: "tutorial"

Explanation: The function lcs_of_three creates a 3D dynamic programming table to calculate the LCS length for every combination of substrings from the three input strings. After filling the table using the recurrence relation, the function backtracks through the table to reconstruct one possible LCS. This approach efficiently computes the result with a time complexity of O(n1*n2*n3).

Conclusion

In this tutorial, we explored a dynamic programming solution to the LCS problem for three strings. We discussed the problem statement, examined sample inputs and outputs with detailed explanations, and provided a complete Python program that computes both the length of the LCS and one possible LCS through backtracking. This method is an excellent extension of the two-string LCS problem and is a valuable technique for DSA interviews.

TutorialKart

Python – LCS of Three Strings