Longest Common Subsequence

The Longest Common Subsequence (LCS) of two sequences is the longest sequence of elements that appears in both, in the same relative order, but not necessarily contiguously. It shows up constantly in practice: diff and version control tools use it to figure out what changed between two file revisions, bioinformatics tools use it to compare DNA or protein sequences, and it is one of the most common “two strings” interview questions because it’s the cleanest introduction to two-dimensional dynamic programming. This lesson builds the recurrence from first principles, explains why a naive recursive solution is too slow, and shows how to both compute the LCS length and reconstruct the actual subsequence.

Overview: How It Works

Consider two short strings, "ABC" and "AC". A subsequence keeps the relative order of characters but can skip any of them, so "AC" is a subsequence of "ABC" (skip the B) — and since "AC" is also the second string itself, the longest common subsequence of these two strings is "AC", with length 2. Contrast this with a substring, which must be contiguous: "AC" is not a substring of "ABC" because the B sits between them. This distinction — subsequence allows gaps, substring does not — is the single most important thing to get right about LCS, and it drives a common mistake covered later in this lesson.

To find the LCS of two strings text1 (length m) and text2 (length n), build a 2D table dp with m + 1 rows and n + 1 columns, where dp[i][j] holds the length of the LCS of the first i characters of text1 and the first j characters of text2. The extra row and column (index 0) represent an empty prefix, and the LCS of anything with an empty string is always 0 — that’s the base case, and it’s why dp is initialized to all zeros.

The key insight is a recurrence with two cases, decided by comparing the last character of each prefix:

• If text1[i - 1] == text2[j - 1] (the last characters of both prefixes match), that character must belong to some optimal LCS, so dp[i][j] = dp[i - 1][j - 1] + 1 — one more than the LCS of both strings with that matching character removed from the end.
• If they don’t match, the LCS of the two prefixes can’t use both last characters together, so it’s the better of dropping one character from either side: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

Filling this table from the base case upward, row by row, is what makes this dynamic programming: each cell is solved exactly once from already-solved smaller subproblems, and the final answer sits in the bottom-right corner, dp[m][n]. A direct recursive translation of the same recurrence, without a table, recomputes the same (i, j) subproblem over and over — the two branches of the “no match” case overlap heavily — which is why the naive recursive version is exponential while the tabulated version is polynomial.

Time and Space Complexity

Approach	Time	Space	Why
Naive recursion (no memo)	O(2^(m + n))	O(m + n)	Every mismatched pair branches into two recursive calls, and each branch only shrinks i or j by 1, so the call tree can double at every level down to a maximum depth of m + n.
Top-down memoized recursion	O(m * n)	O(m * n)	There are only (m + 1) * (n + 1) distinct (i, j) states; memoizing means each is computed once and reused.
Bottom-up 2D table	O(m * n)	O(m * n)	Fills every cell of an (m + 1) x (n + 1) table exactly once, doing O(1) work per cell.
Bottom-up, rolling rows (length only)	O(m * n)	O(min(m, n))	Each row only depends on the row directly above it, so only two rows need to exist in memory at once.

The time complexity is O(m * n), where m and n are the lengths of the two input strings, for every DP-based variant: the algorithm must fill (or visit) every one of the (m + 1) * (n + 1) cells, and each cell does O(1) work (one character comparison, one addition or one max). There’s no early exit, so best, average, and worst case are all O(m * n) — the table has to be fully built regardless of what the strings contain. Space is O(m * n) for the full table, which is required if you need to reconstruct the actual subsequence by backtracking through it afterward. If you only need the length, you can drop space to O(min(m, n)) by keeping just the current and previous row, since every cell in row i only ever looks at row i - 1 and cells already computed in the current row.

Examples

Example 1: LCS Length with a Full 2D Table

This is the standard bottom-up implementation: build the (m + 1) x (n + 1) table and apply the two-case recurrence.

def lcs_length(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]

text1 = "ABCBDAB"
text2 = "BDCABA"
print(lcs_length(text1, text2))

Output:

4

Here text1 = "ABCBDAB" and text2 = "BDCABA". Filling the table row by row (i from 1 to 7, j from 1 to 6) using the recurrence above ends with dp[7][6] = 4, so lcs_length returns 4. One valid LCS of length 4 is "BCBA": B at text1[1]/text2[0], C at text1[2]/text2[2], B at text1[3]/text2[4], and A at text1[5]/text2[5] — the indices increase in both strings, which is exactly what “same relative order” requires.

Example 2: Reconstructing the Actual Subsequence

Knowing the length isn’t always enough — often you need the LCS string itself. After filling the same table, walk backward from dp[m][n], following whichever direction the optimal choice came from.

def lcs_string(text1: str, text2: str) -> str:
    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])

    chars: list[str] = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:
            chars.append(text1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    chars.reverse()
    return "".join(chars)

text1 = "ABCBDAB"
text2 = "BDCABA"
print(lcs_string(text1, text2))

Output:

BCBA

Starting at i = 7, j = 6 (the bottom-right corner) and walking backward: whenever text1[i - 1] == text2[j - 1], that character is recorded and both i and j decrease. Otherwise the pointer moves toward whichever neighboring cell, dp[i - 1][j] or dp[i][j - 1], holds the larger value, since that’s the direction the optimal subsequence came from. Applying this to "ABCBDAB" and "BDCABA" collects the characters A, B, C, B in that reverse order as it walks backward; reversing the collected list gives "BCBA" — matching the length of 4 found in Example 1.

Example 3: Space-Optimized Length-Only Version

When you only need the length, you don’t need the full table — each row only depends on the row above it, so two rolling rows are enough.

def lcs_length_optimized(text1: str, text2: str) -> int:
    if len(text2) > len(text1):
        text1, text2 = text2, text1
    n = len(text2)
    previous = [0] * (n + 1)
    for i in range(1, len(text1) + 1):
        current = [0] * (n + 1)
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                current[j] = previous[j - 1] + 1
            else:
                current[j] = max(previous[j], current[j - 1])
        previous = current
    return previous[n]

text1 = "AGCAT"
text2 = "GAC"
print(lcs_length_optimized(text1, text2))

Output:

2

text2 = "GAC" is already the shorter string, so no swap happens; n = 3. Rolling row by row through all 5 characters of text1, the final row holds [0, 1, 2, 2], so previous[3] = 2 is returned. That matches reality: "AC" and "GC" are both valid common subsequences of length 2, but there’s no length-3 common subsequence. For instance, "GAC" is not a subsequence of "AGCAT": the G is at index 1, the next A after it is at index 3, but the only C in the string is at index 2 — before that A, not after it.

How It Works, Step by Step

Walk through building the table by hand for text1 = "ABC" and text2 = "AC" (m = 3, n = 2). The table has 4 rows (i = 0..3) and 3 columns (j = 0..2); row 0 and column 0 are all zero because the LCS of anything with an empty string is 0.

	“” (j=0)	A (j=1)	C (j=2)
“” (i=0)	0	0	0
A (i=1)	0	1	1
B (i=2)	0	1	1
C (i=3)	0	1	2

Step through the non-trivial cells: at dp[1][1], text1[0] = 'A' matches text2[0] = 'A', so dp[1][1] = dp[0][0] + 1 = 1. At dp[1][2], text1[0] = 'A' doesn’t match text2[1] = 'C', so dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1. Row 2 (character 'B') never matches 'A' or 'C', so it just carries forward the best value seen above it: dp[2][1] = 1, dp[2][2] = 1. Finally, at dp[3][1], text1[2] = 'C' doesn’t match text2[0] = 'A', so dp[3][1] = max(dp[2][1], dp[3][0]) = max(1, 0) = 1; at dp[3][2], text1[2] = 'C' matches text2[1] = 'C', so dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2. The bottom-right cell, dp[3][2] = 2, is the answer: the LCS of "ABC" and "AC" has length 2 (the subsequence "AC" itself).

Common Mistakes

Mistake 1: Off-by-one indexing between the table and the strings

The dp table is 1-indexed (dp[i][j] describes the first i and first j characters) but Python strings are 0-indexed, so the character compared at row i is always text1[i - 1], never text1[i]. Forgetting the offset compares the wrong characters and eventually crashes, since i and j both range up to and including m and n — one past the last valid string index:

def lcs_length_buggy(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] == text2[j]:
                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]

text1 = "ABC"
text2 = "AC"
print(lcs_length_buggy(text1, text2))

As soon as i reaches m (or j reaches n), text1[i] (or text2[j]) indexes one past the end of the string and Python raises IndexError: string index out of range. The fix is to always read text1[i - 1] and text2[j - 1] inside the loop:

def lcs_length_fixed(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]

text1 = "ABC"
text2 = "AC"
print(lcs_length_fixed(text1, text2))

Output:

2

Mistake 2: Solving “longest common substring” instead of “longest common subsequence”

It’s tempting to reset dp[i][j] to 0 on a mismatch, the way you would for the longest common substring problem (which requires contiguous characters). For LCS, that’s wrong: a mismatch should still carry forward the best result found so far via max(...), because the subsequence is allowed to skip characters instead of resetting.

def lcs_length_wrong(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 0
    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
                best = max(best, dp[i][j])
            else:
                dp[i][j] = 0
    return best

text1 = "ABCBDAB"
text2 = "BDCABA"
print(lcs_length_wrong(text1, text2))

For these strings this buggy version returns 2 (the longest run of contiguous shared characters), not 4, because resetting to 0 on every mismatch forbids skipping over characters. The fix is to carry forward the best of the two neighboring cells on a mismatch instead of discarding progress:

def lcs_length_correct(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]

text1 = "ABCBDAB"
text2 = "BDCABA"
print(lcs_length_correct(text1, text2))

Output:

4

Best Practices

• Reach for the LCS pattern whenever a problem compares two sequences that must keep relative order but may skip elements freely — diffing tools, DNA/protein alignment, and “edit two strings into each other” problems all build on it.
• If you only need the length, use the space-optimized rolling-row version (O(min(m, n)) space); only build the full 2D table when you need to reconstruct the actual subsequence, since backtracking requires the whole table.
• Always initialize row 0 and column 0 to zero explicitly (or via a table built with an extra row/column) — they represent the base case of comparing against an empty string, and skipping them breaks the recurrence.
• Prefer the iterative bottom-up table over naive top-down recursion for long strings; Python’s recursion limit (around 1000) can be hit by deep recursive calls, and the bottom-up version avoids recursion entirely.
• Never use a mutable default argument like def lcs_memo(i, j, memo={}) for a memoized recursive version — the dictionary is shared and persists across separate calls with different input strings. Pass the memo dict explicitly, or use functools.lru_cache.
• Remember LCS is a building block: longest palindromic subsequence, shortest common supersequence, and Levenshtein-style edit distance all reduce to or extend this same table.

Practice Exercises

1. Reconstruct alongside the length. Extend lcs_length so it also returns one valid LCS string, using the backtracking approach from Example 2. Test it on "AGGTAB" and "GXTXAYB" — the length should be 4, and a valid answer is "GTAB".
2. Shortest Common Supersequence length. Given two strings, find the length of the shortest string that contains both as subsequences. Hint: it equals len(text1) + len(text2) - lcs_length(text1, text2), since every LCS character is shared and only needs to appear once in the supersequence. For "ABC" and "AC", the expected length is 3.
3. Longest Palindromic Subsequence. A string’s longest palindromic subsequence equals the LCS of that string and its reverse. Implement it by calling lcs_length with s and s[::-1]. Test it on "BBBAB" — the expected length is 4 (one valid palindromic subsequence is "BBBB").

Summary

• The Longest Common Subsequence (LCS) of two strings is the longest sequence of characters common to both that preserves relative order but doesn’t need to be contiguous — that’s what separates it from “longest common substring.”
• Core recurrence: if text1[i - 1] == text2[j - 1], then dp[i][j] = dp[i - 1][j - 1] + 1; otherwise dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]), with row 0 and column 0 initialized to 0.
• Time complexity is O(m * n) for every DP-based approach, since the table has (m + 1) * (n + 1) cells and each does O(1) work; best, average, and worst case are all the same because the whole table must be filled regardless of input.
• Space is O(m * n) for the full table (needed to reconstruct the subsequence), or O(min(m, n)) if only the length is needed, using rolling rows.
• A naive, unmemoized recursive solution is exponential, O(2^(m + n)), because it recomputes the same (i, j) subproblems repeatedly; memoizing or tabulating is what makes LCS tractable.
• LCS underlies other classic problems: longest palindromic subsequence, shortest common supersequence, and diff-style edit distance all build on this same table.