Python - Space-Optimized LCS

Python – Space-Optimized LCS

The Longest Common Subsequence (LCS) problem is a classic dynamic programming challenge where you determine the longest sequence of characters that appear left-to-right (but not necessarily consecutively) in two strings. In this tutorial, we focus on a space-optimized solution that reduces memory usage from O(m*n) to O(n) by utilizing a one-dimensional DP array. This approach is especially beneficial for interview problems and large input sizes.

Problem Statement

Given two strings s1 and s2, find the length of their longest common subsequence. The LCS is the longest sequence of characters that appears in both strings in the same order, though not necessarily contiguously.

Sample Input and Output

Example 1:

</>

Copy

# Input:
s1 = "ABCBDAB"
s2 = "BDCABA"

# Calculation:
# One possible LCS is "BCBA", which has a length of 4.

# Output:
4

Explanation: The two strings share several common subsequences. The longest one found here, “BCBA” (or an equivalent sequence), has 4 characters. The space-optimized algorithm computes this length without needing to store an entire 2D table.

Example 2:

</>

Copy

# Input:
s1 = "AGGTAB"
s2 = "GXTXAYB"

# Calculation:
# The LCS is "GTAB", which has a length of 4.

# Output:
4

Explanation: For these input strings, the longest common subsequence identified is “GTAB” with a length of 4. The algorithm efficiently finds the LCS length using a minimal amount of extra space.

Solution Approach

The traditional DP solution for LCS uses a 2D table to store subproblem results, requiring O(m*n) space. However, we can optimize this by noticing that each row only depends on the previous row. Therefore, a one-dimensional DP array is sufficient. We update this array in place while using a temporary variable to hold the value from the previous iteration, ensuring we have access to the needed previous row’s data.

Python Program

Space-Optimized LCS Function

</>

Copy

def lcs_space_optimized(s1, s2):
    """
    Compute the length of the Longest Common Subsequence (LCS) between two strings
    using a space-optimized dynamic programming approach.

    Parameters:
    s1 (str): First string.
    s2 (str): Second string.

    Returns:
    int: Length of the LCS.
    """
    m, n = len(s1), len(s2)
    # Initialize a 1D DP array with zeros. dp[j] represents the LCS length for s1[0..i] and s2[0..j].
    dp = [0] * (n + 1)

    # Iterate over each character in s1.
    for i in range(1, m + 1):
        prev = 0  # 'prev' holds dp[j-1] from the previous iteration (i-1 row).
        for j in range(1, n + 1):
            temp = dp[j]  # Store current dp[j] before updating.
            if s1[i - 1] == s2[j - 1]:
                # If characters match, extend the LCS by 1.
                dp[j] = prev + 1
            else:
                # Otherwise, take the maximum LCS so far from left or top.
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp  # Update 'prev' to the old dp[j] value for the next iteration.
    return dp[n]

# Test the function with sample examples

print("Example 1:")
s1 = "ABCBDAB"
s2 = "BDCABA"
print("Input strings:", s1, "and", s2)
print("Length of LCS:", lcs_space_optimized(s1, s2))  # Expected output: 4

print("\nExample 2:")
s1 = "AGGTAB"
s2 = "GXTXAYB"
print("Input strings:", s1, "and", s2)
print("Length of LCS:", lcs_space_optimized(s1, s2))  # Expected output: 4

Explanation: In this implementation, we maintain a one-dimensional list dp where each dp[j] represents the length of the LCS for the current segment of s1 and s2. The variable prev temporarily holds the value of dp[j-1] from the previous row, ensuring that when characters match (s1[i-1] == s2[j-1]), we can correctly update dp[j] as prev + 1. Otherwise, we update dp[j] as the maximum of the current value and dp[j-1]. This method efficiently computes the LCS length using O(n) extra space.

Conclusion

The space-optimized dynamic programming approach for the LCS problem significantly reduces memory usage while maintaining an O(m*n) time complexity. This tutorial provided a comprehensive explanation, sample inputs and outputs, and a complete Python implementation designed for beginners. Understanding this method is essential for tackling similar DP problems in technical interviews.

TutorialKart

Python – Space-Optimized LCS