Longest Common Subsequence — InterviewPrepKit

Solving tips

This is the archetype two-string alignment DP: dp[i][j] = LCS length of text1[:i] and text2[:j] on a prefix grid.
On a match take the diagonal plus one (dp[i-1][j-1]+1); on a mismatch take max(dp[i-1][j], dp[i][j-1]) — do not use max on a match, which silently drops valid pairings.
Empty-prefix row and column are all zeros; target O(m*n) time, O(min(m,n)) space with two rolling rows.
Pitfall: confusing subsequence (allows gaps) with substring (contiguous, uses a reset-to-0-on-mismatch recurrence).

Problem

Given two strings text1 and text2, return the length of their longest common subsequence (LCS). A subsequence keeps characters in their original relative order but may skip any number of them (it need not be contiguous). A common subsequence is one that appears in both strings.

If there is no common subsequence, return 0.

Examples

text1 = "abcde", text2 = "ace" → 3 — "ace" is a subsequence of both.
text1 = "abc", text2 = "abc" → 3 — identical strings; the whole string is the LCS.
text1 = "abc", text2 = "def" → 0 — no shared characters at all.

Constraints

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

Lengths up to 1000 each mean the expected solution is O(m × n) — up to a million cells.

Think about it first

Hint 1

Compare the last characters. If they are equal, that pair can be the tail of the LCS — count it and recurse on both shorter prefixes. If they differ, at least one of those two characters is not in the LCS, so try dropping each and keep the better result.

Hint 2

The subproblem is "LCS length of `text1`'s first `i` characters and `text2`'s first `j` characters." Two prefix lengths → a 2-D table `dp[i][j]`.

Hint 3

If `text1[i-1] == text2[j-1]`: `dp[i][j] = 1 + dp[i-1][j-1]`. Otherwise `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`. The row and column for an empty prefix are all zeros.

TL;DR

Classic LCS DP over prefix pairs (i, j) — O(m × n) time, O(min(m, n)) space after rolling to two rows.

Approach 1 — Brute-force recursion

Intuition: compare the current last characters. Equal → they extend the LCS, so add 1 and shrink both. Unequal → drop the last character of one string or the other and keep whichever gives more.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        def dfs(i: int, j: int) -> int:
            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))

Complexity: O(2^(m+n)) time worst case, O(m+n) recursion depth.

Why the constraints kill it: two length-1000 strings with few matches branch into an astronomically large tree.

Approach 2 — Top-down memoization

The insight: only (i, j) varies, giving (m+1)(n+1) distinct subproblems. Cache them and the tree collapses into the grid.

from functools import lru_cache


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        @lru_cache(maxsize=None)
        def dfs(i: int, j: int) -> int:
            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))

Complexity: O(m × n) time and space.

Approach 3 — Bottom-up 2-D table

Table meaning: dp[i][j] = length of the LCS of text1[:i] and text2[:j].

2-D recurrence:

dp[i][0] = 0,  dp[0][j] = 0                 # empty prefix shares nothing
if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1             # extend the diagonal match
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # best of dropping one char

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]

Walkthrough on text1 = "abcde", text2 = "ace":

	a	c	e
""	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

The diagonal bumps at a, c, e build up to dp[5][3] = 3.

Complexity: O(m × n) time, O(m × n) space.

Approach 4 — Space-optimized two rows

The insight: each cell reads only the previous row and the current row’s left neighbor, so two rows suffice. Keep prev and fill curr.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        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: O(m × n) time, O(n) space. (Iterate over the longer string as the outer loop and the shorter as inner for O(min(m, n)) space.)

Common pitfalls

Using max on the diagonal for a match — when characters match you must take dp[i-1][j-1] + 1; taking max(dp[i-1][j], dp[i][j-1]) there silently drops valid pairings.
Confusing subsequence with substring — LCS allows gaps; the longest common substring problem uses a different recurrence (reset to 0 on mismatch).
Index vs length off-by-one — dp[i][j] uses characters text1[i-1] and text2[j-1]; mixing 0-based and 1-based indexing here is the classic bug.
In the rolled version, allocate a fresh curr (or clear it) each row so stale values don’t leak in.

Pattern takeaway

LCS is the archetype 2-D string DP: a match walks the diagonal and adds one, a mismatch takes the max of the two orthogonal neighbors. This same grid underlies edit distance, interleaving, and diff tools — recognize “align two sequences, order-preserving” and reach for the (i, j) prefix table.