# Longest Common Subsequence: DP Solution and Space Optimization

Source: https://www.techinterview.org/post/3233460129/longest-common-subsequence-dp-solution-and-space-optimization/
Updated: 2026-04-16 · techinterview.org

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](https://www.techinterview.org/post/3233460130/edit-distance-levenshtein-dp-solution-explained/) — same 2D DP table structure as LCS; edit distance = m + n - 2*LCS when only insert/delete are allowed
- [0/1 Knapsack](https://www.techinterview.org/post/3233460128/0-1-knapsack-problem-dp-solution-with-space-optimization/) — both use 2D DP where rows = items/characters and columns = capacity/position; understand the state transition differences