DSA Guide
Dynamic Programming

Longest Common Subsequence

The 2-D DP table that underlies diff tools — compare two strings by asking one question per character pair

MediumDynamic Programming· two-sequence table
StringDynamic Programming
Problem #1143

Problem Statement

Return the length of the longest subsequence present in both strings. A subsequence keeps the original order but may skip characters.

Input:  text1 = "abcde", text2 = "ace"
Output: 3          "ace"

Input:  text1 = "abc", text2 = "abc"
Output: 3

Input:  text1 = "abc", text2 = "def"
Output: 0

Subsequence, not substring

"ace" is a subsequence of "abcde" — the characters appear in order with gaps. It is not a substring, because substrings must be contiguous.

That distinction decides the whole approach. Substring problems often yield to a sliding window; subsequence problems almost never do, because gaps mean there are 2ⁿ possibilities rather than n².

Intuition

Brute force: generate every subsequence of the first string and check each against the second. There are 2ⁿ of them. At 20 characters that is a million; at 1,000 it is beyond counting.

Instead, look at just the last character of each string. There are only two cases.

"abcde"  vs  "ace"
      ↑          ↑
      e          e      SAME

If the last characters match, that character is definitely in the answer — so the answer is 1 + the LCS of both strings with that character removed.

"abcd"  vs  "ace"
     ↑         ↑
     d         e        DIFFERENT

If they differ, at least one of them is not in the answer. Try dropping each and keep the better result: max(LCS without d, LCS without e).

The insight

if a[i] == b[j]:  lcs(i, j) = 1 + lcs(i-1, j-1)      ← both shrink
else:             lcs(i, j) = max(lcs(i-1, j),        ← drop from a
                                  lcs(i, j-1))        ← drop from b

Every subproblem is "some prefix of A against some prefix of B" — and there are only m × n such pairs. The 2ⁿ explosion was almost entirely recomputation.

That is the move worth taking away: when a problem compares two sequences, the subproblem is usually a pair of prefixes. A 2-D table follows automatically.

Approach

Build an (m+1) × (n+1) table

The extra row and column represent "an empty prefix", which makes the base cases free — an empty string shares nothing with anything, so those are all 0.

Fill row by row

Row i, column j answers: what is the LCS of the first i characters of A and the first j of B?

Characters match → take the diagonal plus one

table[i][j] = table[i-1][j-1] + 1. The diagonal is "both strings one shorter".

Characters differ → take the better neighbour

table[i][j] = max(table[i-1][j], table[i][j-1]) — above means "skip A's character", left means "skip B's".

The bottom-right cell is the answer

text1 = "ace" (rows), text2 = "abcde" (columns)
012345
0
1
0
0
0
0
0
2
0
0
0
0
0
3
0
0
0
0
0
setuprow 0 and column 0 are all zero
The padding row and column mean 'compared against an empty string'. Nothing is in common with nothing, so they are 0 — and no special case is needed later.
1 / 4
15 cells, one comparison each. The brute force would have tested 8 subsequences of 'ace' against 32 of 'abcde'.

Solution

def longest_common_subsequence(text1: str, text2: str) -> int:
    """Length of the longest subsequence common to both strings.

    table[i][j] = LCS of text1[:i] and text2[:j]. The extra row and
    column of zeros represent empty prefixes.
    """
    m, n = len(text1), len(text2)
    table = [[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]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])

    return table[m][n]

Note text1[i - 1]: the table is 1-indexed because of the padding row, while the string is 0-indexed. Mixing these up is the most common bug on this problem.

Why the padding row and column are worth the extra memory

Without them, every cell touching an edge needs a bounds check:

top = table[i-1][j] if i > 0 else 0
left = table[i][j-1] if j > 0 else 0

With them, table[0][j] and table[i][0] are real cells that already hold 0. The loop body has no conditionals about position at all.

Trading one row and one column for the removal of every edge case is nearly always worth it in 2-D DP.

Complexity Analysis

Time Complexity

O(m × n)

Space Complexity

O(m × n)

Time — every cell filled once with one comparison. For two 1,000-character strings that is a million operations, against 2¹⁰⁰⁰ for the brute force.

Space — the table. Reducible to O(min(m, n)) by keeping two rows, since each row only reads the one above it. Not worth it unless memory is genuinely tight — the two-row version is noticeably harder to read.

Edge Cases

Unique Paths

Count the routes across a grid — the clearest introduction to filling a 2-D table, where each cell is the sum of two neighbours

Word Break

Can a string be cut into dictionary words? A boolean DP where each position asks about every earlier one

On this page

Problem StatementIntuitionApproachBuild an (m+1) × (n+1) tableFill row by rowCharacters match → take the diagonal plus oneCharacters differ → take the better neighbourThe bottom-right cell is the answerSolutionComplexity AnalysisEdge CasesRelated Problems