Longest Common Subsequence — Solution

Problem

Given two strings, find the length of the longest subsequence that appears in both — a subsequence keeps characters in their original order but doesn't require them to be contiguous. For example, "ace" is a valid subsequence of "abcde" because a, c, and e appear left-to-right with possible gaps.

• Input: text1 = "abcde", text2 = "ace"
• Output: 3
• Explanation: The longest common subsequence is "ace", which has length 3.

Counter-example: text1 = "abc", text2 = "def" → output 0 because no characters are shared.

Intuition

When two characters match, we can extend whatever LCS existed before those positions. When they don't match, we try skipping one character from either string and take the better result. This optimal substructure — "the LCS up to position i, j depends only on earlier sub-problems" — is what makes bottom-up DP efficient here.

Approach 1 — 2D Dynamic Programming

Build a 2D table where dp[i][j] stores the LCS length for text1[:i] and text2[:j]. Fill it row by row: either extend a match diagonally or inherit the best result from skipping one character.

1. Create a (len(text1)+1) × (len(text2)+1) table of zeros — the zero border represents the empty-string base case.
2. For each character pair (text1[i-1], text2[j-1]):
   • If they match: dp[i][j] = 1 + dp[i-1][j-1].
   • If they don't: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
3. Return dp[len(text1)][len(text2)].

1def longestCommonSubsequence(text1: str, text2: str) -> int:
2    rows, cols = len(text1), len(text2)
3    dp = [[0] * (cols + 1) for _ in range(rows + 1)]
4
5    for i in range(1, rows + 1):
6        for j in range(1, cols + 1):
7            if text1[i - 1] == text2[j - 1]:
8                dp[i][j] = 1 + dp[i - 1][j - 1]  # characters match, extend the prior LCS
9            else:
10                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # skip one character, keep the best
11
12    return dp[rows][cols]

Time: O(m × n) — every cell in the table is filled exactly once.
Space: O(m × n) — the full table is held in memory throughout.

Approach 2 — Space-Optimized Rolling Array

Each row only reads from the row directly above and the cell to its left, so we can discard older rows and keep only two at a time.

1. Swap text1 and text2 if text2 is longer, so the shorter string determines the array length.
2. Keep prev_row (the row above) and fill a fresh curr_row for each character in text1.
3. After processing each character, set prev_row = curr_row.
4. Return prev_row[len(text2)].

1def longestCommonSubsequence(text1: str, text2: str) -> int:
2    if len(text2) > len(text1):
3        text1, text2 = text2, text1  # keep the shorter string as text2 to minimize array size
4
5    prev_row = [0] * (len(text2) + 1)
6
7    for char1 in text1:
8        curr_row = [0] * (len(text2) + 1)
9        for j, char2 in enumerate(text2, 1):
10            if char1 == char2:
11                curr_row[j] = 1 + prev_row[j - 1]  # diagonal: both characters contributed
12            else:
13                curr_row[j] = max(prev_row[j], curr_row[j - 1])
14        prev_row = curr_row
15
16    return prev_row[len(text2)]

Time: O(m × n) — same computation, just without retaining old rows.
Space: O(min(m, n)) — only two arrays of length min(m, n) + 1 are live at once.

Complexity Summary

Common Mistakes

• Off-by-one between the table and the strings — dp[i][j] covers characters up to index i and j, so the comparison uses text1[i-1] and text2[j-1], not text1[i].
• Only skipping in one direction when characters don't match — returning just dp[i-1][j] misses the path where you skip from text2; you must take max(dp[i-1][j], dp[i][j-1]).
• Confusing subsequence with substring — "ace" is a valid common subsequence of "abcde" even though the characters aren't adjacent; the DP correctly allows gaps between matched characters.
• Overwriting the diagonal in a single-array in-place update — if you update left-to-right in place, dp[j-1] is already overwritten before it's needed as the diagonal for the current match; the two-array approach sidesteps this entirely.
• Forgetting to swap so text2 is the shorter string — in the rolling-array version the array length equals len(text2), so failing to swap wastes memory proportional to the length difference.

Related Problems

• edit-distance — uses the same 2D DP structure over two strings, extending it to count insertions, deletions, and substitutions
• longest-increasing-subsequence — same subsequence concept applied to a single sequence with a numeric ordering constraint
• interleaving-string — 2D DP over two strings checking a structural property rather than matching characters
• palindromic-substrings — DP over substrings that shares the "extend from a sub-problem" recurrence pattern
• maximal-square — 2D grid DP where each cell depends on its neighbors, the same dependency shape as LCS