1143. Longest Common Subsequence

1143

MediumTwo-Dimensional Dynamic Programming2D dynamic programmingSequence-alignment grid DP

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence, or 0 if there is none. A subsequence keeps characters in their original relative order but may drop any number of them; it need not be contiguous. A common subsequence is one that appears in both strings.

Open official problem prompt ↗

In plain English

We want the length of the longest string that can be obtained by deleting characters (without reordering) from both inputs.

Picture it like this

Like diffing two versions of a document: you scan both left to right and keep the longest run of lines that appear in both, in the same order.

Example

Input: text1 = "abcde", text2 = "ace"
Output: 3
Why: "ace" appears in both strings in order, and no common subsequence is longer.

Constraints

1 <= text1.length, text2.length <= 1000text1 and text2 consist of lowercase English characters.

Pattern lesson

See the pattern, then code

Sequence-alignment grid DP

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Compare the last characters. If they match, that character can end the LCS, so add 1 to the LCS of the two shorter prefixes; if not, the answer is the better of dropping the last character of one string or the other.

New words, made simpleKnow these before the algorithm

Subsequence: Characters kept in original order but not necessarily adjacent.
Prefix: The first i characters of a string, text1[:i].
Overlapping subproblems: The same prefix pair is needed by many larger cells, so we cache it in a table.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute-force recursion

Exponential because it recomputes the same prefix pairs repeatedly.

Recurse on both strings, branching on match vs. skipping a character from each side.

Time O(2^(m+n))Space O(m+n)

Best choice2D bottom-up DP

Each prefix pair is computed once; this is the standard optimal solution.

Fill an (m+1) x (n+1) table where dp[i][j] is the LCS of the two prefixes.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

dp[i][j] always equals the LCS length of text1[:i] and text2[:j] before any larger cell reads it.

Why this is correct

Reasoning

The LCS of two prefixes either ends in their shared last character (then it extends the LCS of the smaller prefixes by one) or it does not use one of those last characters (then dropping that character cannot lose any answer). Taking the max over these exhaustive cases yields the optimum.

The algorithm in three movesSay these aloud before coding

1Build a table dp[i][j] = LCS length of text1[:i] and text2[:j], with row/column 0 as zeros

match 'a': dp=1

2For each pair of prefix lengths, if the current characters match set dp[i][j] = dp[i-1][j-1] + 1

match 'c': dp=2

3Otherwise set dp[i][j] = max(dp[i-1][j], dp[i][j-1])

match 'e': dp=3

4Return dp[m][n]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readtext1[0]='a', text2[0]='a'

2 · AskDo the current last characters match?

3 · Update statedp[1][1] built from dp[0][0]+1

4 · Resultdp[1][1] = 1

Key takeaway

The characters a, c, e are matched in order across both strings to form the length-3 LCS.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Allocate the padded table
The extra row and column of zeros represent an empty prefix, giving clean base cases.
2
Lines 7-8Character match
A shared character extends the diagonal predecessor by one.
3
Lines 9-10Character mismatch
Take the best answer that drops the last character from one side or the other.
4
Lines 11Return
The bottom-right cell covers both full strings.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No shared characters at all returns 0
One string is a subsequence of the other returns the shorter length
Repeated characters like text1="aaa", text2="aa" returns 2

Common beginner mistakes

Confusing subsequence with substring and forcing contiguity
Off-by-one errors indexing text1[i-1] vs text1[i] against the padded table
Trying to reconstruct the actual string when only its length is asked

Check your understanding

Why is it safe to take max(dp[i-1][j], dp[i][j-1]) on a mismatch instead of also considering dp[i-1][j-1]?

Longest Common Subsequence

Longest Common Subsequence

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming