roadmap/dynamic-programming/Longest Common Subsequence

Longest Common Subsequence

MediumAmazonGoogleMicrosoftMeta

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence doesn't need to be contiguous.

Intuition — the key insight

dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]. If last chars match: dp[i][j] = dp[i-1][j-1] + 1. Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — skip one char from either string.

Approach

2D DP table

Build (m+1)×(n+1) table. dp[0][*] = dp[*][0] = 0. Fill row by row: match → diagonal+1, no match → max of left/above.

Complexity

Time

O(m×n)

Space

O(m×n) or O(min(m,n)) with rolling

Fill every cell once. Can optimize space to O(n) using two rows.

Solution code

Python

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[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]

Edge cases to remember

⚠Empty string: LCS is 0

⚠Identical strings: LCS = length

⚠No common chars: LCS is 0

Hints

What pattern do you think this problem uses?