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 = "abcde", text2 = "ace" (the first example) one cell at a time: watch which of the three sources — diagonal, above, or left — supplies each value.
dp table (i = text1 prefix, j = text2 prefix)
diagonal
dp[0][0] = 0
match only, +1
used
above
dp[0][1] = 0
drops a text1 char
not used
left
dp[1][0] = 0
drops a text2 char
not used
Base row and column are 0 since an empty prefix shares nothing. text1[0] a matches text2[0] a, so dp[1][1] = dp[0][0] + 1 = 1.
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.