Longest Common Subsequence

Difficulty: Medium Source: NeetCode

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence that can be derived from the original string by deleting some (or no) characters without changing the relative order of the remaining characters. If there is no common subsequence, return 0.

Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The LCS is "ace".

Example 2: Input: text1 = "abc", text2 = "abc" Output: 3

Example 3: Input: text1 = "abc", text2 = "def" Output: 0

Constraints:

• 1 <= text1.length, text2.length <= 1000
• Both strings consist of only lowercase English letters.

Prerequisites

Before attempting this problem, you should be comfortable with:

• 2D DP — filling a table based on two sequences
• Subsequences vs Substrings — a subsequence doesn’t need to be contiguous

1. Brute Force / Recursive

Intuition

Compare characters from the end of both strings. If they match, this character is part of the LCS — take it and move both pointers inward. If they don’t match, try skipping one character from either string and take the better result. This naturally explores all possible pairings, but overlapping subproblems make it exponential.

Algorithm

1. Define dfs(i, j) = LCS length for text1[:i] and text2[:j].
2. Base case: if i == 0 or j == 0, return 0.
3. If text1[i-1] == text2[j-1], return 1 + dfs(i-1, j-1).
4. Else return max(dfs(i-1, j), dfs(i, j-1)).

Solution

def longestCommonSubsequence(text1, text2):
    def dfs(i, j):
        if i == 0 or j == 0:
            return 0
        if text1[i - 1] == text2[j - 1]:
            return 1 + dfs(i - 1, j - 1)
        return max(dfs(i - 1, j), dfs(i, j - 1))

    return dfs(len(text1), len(text2))


print(longestCommonSubsequence("abcde", "ace"))  # 3
print(longestCommonSubsequence("abc", "abc"))    # 3
print(longestCommonSubsequence("abc", "def"))    # 0

Complexity

• Time: O(2^(m+n)) — exponential without memoization
• Space: O(m+n) — recursion stack

2. Bottom-Up DP (Tabulation)

Intuition

Create a (m+1) x (n+1) table where dp[i][j] is the LCS length of text1[:i] and text2[:j]. The extra row and column of zeros are our base cases (empty string LCS is 0). Fill the table row by row using the recurrence: if characters match, take the diagonal + 1; if not, take the max of the cell above or to the left. The answer is in dp[m][n].

Algorithm

1. Create dp of size (m+1) x (n+1) filled with 0.
2. For i in 1..m, for j in 1..n:
   • If text1[i-1] == text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
   • Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. Return dp[m][n].

Solution

def longestCommonSubsequence(text1, text2):
    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] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]


print(longestCommonSubsequence("abcde", "ace"))  # 3
print(longestCommonSubsequence("abc", "abc"))    # 3
print(longestCommonSubsequence("abc", "def"))    # 0
print(longestCommonSubsequence("", "abc"))       # 0

Complexity

• Time: O(m * n)
• Space: O(m * n) — reducible to O(n) with two alternating rows

Common Pitfalls

Confusing indices. text1[i-1] corresponds to row i in the (m+1) x (n+1) table. The +1 offset is there so row 0 and column 0 act as the empty-string base case — don’t mix up i and i-1.

Using max(above, left, diagonal). The diagonal is only valid when characters match. When they don’t, you choose between above and left — the diagonal is not a candidate.

Thinking LCS must be contiguous. The LCS is a subsequence, meaning characters can be spread across the string. It’s not a substring. “abcde” and “ace” share LCS “ace” even though there are gaps.