DSAPrep
Medium2-D DP

Longest Common Subsequence

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. For example, ace is a subsequence of abcde.

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters.
View original on LeetCode ↗

For two positions i in text1 and j in text2: if the characters match, they extend the best subsequence found before both of them by one. If they do not match, the best answer so far either drops the current character of text1 or drops the current character of text2 — whichever leaves the longer subsequence.

Brute Force Recursion

Time O(2^(m+n))Space O(m+n)

At each pair of indices (i, j), branch: if text1[i] == text2[j], that character is definitely part of an optimal subsequence, so take it and recurse on (i+1, j+1). Otherwise try skipping a character from either string and keep the better result.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def lcs(i: int, j: int) -> int:
            if i == len(text1) or j == len(text2):
                return 0
            if text1[i] == text2[j]:
                return 1 + lcs(i + 1, j + 1)
            return max(lcs(i + 1, j), lcs(i, j + 1))
        return lcs(0, 0)

Each call branches into two more, and the same (i, j) pair is revisited many times through different paths — exponential blow-up.

2-D DP Table (Bottom-Up)

OptimalTime O(m·n)Space O(m·n)

Cache the answer for every (i, j) pair instead of recomputing it. dp[i][j] holds the LCS length of text1[0:i] and text2[0:j]. Row 0 and column 0 are base cases — an empty prefix shares no characters with anything, so they stay 0.

class Solution:
    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]

Filling the table for text1 = "abc", text2 = "bc" (a small illustrative pair, distinct from the examples above):

0
0
0
·
·
·
·
·
·
·
·
·
1 / 7
comparingseenresultcurrent

Base case: row 0 and column 0 are 0 because an empty prefix has no common subsequence with anything.

Complexity: each of the (m+1)·(n+1) cells does O(1) work → O(m·n) time, O(m·n) space.

Space-Optimized DP

Time O(m·n)Space O(min(m, n))

Each row of the table only depends on the row directly above it. Keep just two 1-D rows (or one, updated carefully) instead of the full grid — using the shorter string as the column dimension keeps the row as small as possible.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) < len(text2):
            text1, text2 = text2, text1
        n = len(text2)
        prev = [0] * (n + 1)
        for ch1 in text1:
            curr = [0] * (n + 1)
            for j, ch2 in enumerate(text2, 1):
                if ch1 == ch2:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev = curr
        return prev[n]

Same O(m·n) time, but only two rows of length min(m, n) + 1 are ever alive — O(min(m, n)) space.