LeetEye LeetEye
Medium 2D Dynamic Programming ~5 min

Longest Common Subsequence

2d-dp longest-common-subsequence

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Examples

Example 1
Input: text1 = "abcde", text2 = "ace"
Output: 3
The longest common subsequence is "ace".
Example 2
Input: text1 = "abc", text2 = "abc"
Output: 3
Example 3
Input: text1 = "abc", text2 = "def"
Output: 0
Key Insight

If characters match, extend LCS by 1. Otherwise, take max of excluding each character.

Match → dp[i-1][j-1] + 1. No match → max(dp[i-1][j], dp[i][j-1]). Classic 2D DP on two strings.

How to Approach This Problem

Pattern Recognition: When you see keywords like longest common subsequence 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 If text1[i-1] == text2[j-1], then:
Answer: dp[i][j] = dp[i-1][j-1] + 1
Matching characters extend the LCS by 1.
2 If text1[i-1] != text2[j-1], then:
Answer: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Characters don't match, so skip one character from either string. Take the better result.
3 dp[0][j] and dp[i][0] should be:
Answer: 0
Empty string has no common subsequence with anything. LCS = 0.
4 When chars don't match, we try both dp[i-1][j] and dp[i][j-1] because:
Answer: All of above
Either character might be useless for the LCS. Try excluding each.
5 dp[i][j] represents LCS of:
Answer: text1[0:i] and text2[0:j]
1-indexed DP where dp[i][j] = LCS of first i chars of text1, first j chars of text2.

Solution

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    
    # Space-optimized: only need previous row
    prev = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr
    
    return prev[n]

Complexity Analysis

Time O(m × n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye