Longest Common Subsequence: DP Solution and Space Optimization

By /

Longest Common Subsequence (LCS) is a fundamental string DP problem that appears in interviews at Google, Microsoft, and Amazon — and is the algorithm behind git diff, DNA sequence alignment, and file comparison tools. Mastering LCS gives you the template for edit distance and a family of sequence alignment problems.

Problem

Find the length of the longest subsequence present in both strings. A subsequence doesn’t need to be contiguous.

s1 = "ABCBDAB"
s2 = "BDCABA"
LCS = "BCBA" or "BDAB" (length 4)

2D DP Solution

def lcs_length(s1: str, s2: str) -> int:
    """
    dp[i][j] = LCS length for s1[:i] and s2[:j].
    If characters match: dp[i][j] = dp[i-1][j-1] + 1
    If not: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    Time: O(m * n), Space: O(m * n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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]

def lcs_string(s1: str, s2: str) -> str:
    """Reconstruct the actual LCS string by backtracking through dp table."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Backtrack
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            result.append(s1[i - 1])
            i -= 1; j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(result))

print(lcs_length("ABCBDAB", "BDCABA"))  # 4
print(lcs_string("ABCBDAB", "BDCABA"))  # BCAB or BDAB

Space Optimization: O(min(m, n))

def lcs_space_optimized(s1: str, s2: str) -> int:
    """
    Use two rows instead of full m*n table.
    Ensures s2 is the shorter string for minimum space.
    Space: O(min(m, n))
    """
    if len(s1) < len(s2):
        s1, s2 = s2, s1  # s2 is always shorter

    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)

    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr

    return prev[n]

Relationship to Other Problems

Problem Relationship to LCS
Edit Distance (LCS ↔ Levenshtein) Min edits = m + n – 2 * LCS(s1, s2) for substitution-free case; similar DP structure
Shortest Common Supersequence SCS length = m + n – LCS(s1, s2); LCS positions are shared
Longest Increasing Subsequence (LIS) LIS can be reduced to LCS of array and its sorted version
Delete Minimum Characters to Make Anagram LCS gives characters to keep; delete the rest

Practice Problems

  • LeetCode 1143: Longest Common Subsequence
  • LeetCode 1092: Shortest Common Supersequence (return the actual string)
  • LeetCode 583: Delete Operation for Two Strings (min deletions = m + n – 2*LCS)
  • LeetCode 1035: Uncrossed Lines (equivalent to LCS)

Related DP Problems

  • Edit Distance — same 2D DP table structure as LCS; edit distance = m + n – 2*LCS when only insert/delete are allowed
  • 0/1 Knapsack — both use 2D DP where rows = items/characters and columns = capacity/position; understand the state transition differences
Scroll to Top