AlgoMaster Logo

Longest Common Subsequence

mediumFrequency9 min readUpdated June 23, 2026

Understanding the Problem

We have two strings and need to find the longest sequence of characters that appears in both, in the same order, but not necessarily consecutively. This is different from the longest common substring problem, where characters must be consecutive.

For instance, given "abcde" and "ace", the character a appears in both, c appears in both after a, and e appears in both after c. So "ace" is a common subsequence of length 3. There is no common subsequence of length 4, so the answer is 3.

This problem has optimal substructure. If we compare the last characters of both strings and they match, then the LCS includes that character plus the LCS of the remaining prefixes. If they don't match, the LCS is the better of two choices: skip the last character of the first string, or skip the last character of the second string. That recursive structure is what makes dynamic programming a good fit.

Key Constraints:

  • 1 <= text1.length, text2.length <= 1000 -> With m and n up to 1000, an O(m * n) solution runs about 1 million operations, which is fast. An O(2^(m+n)) brute force is far too slow at this size, so memoization or tabulation is required.
  • text1 and text2 consist of only lowercase English characters. -> Plain byte comparison works; no Unicode or case handling needed.

Approach 1: Brute Force (Recursion)

Intuition

Solve the problem recursively from the end of both strings. Compare the last two characters. If they match, that character is part of the LCS, so add 1 and recurse on the remaining prefixes. If they don't match, there are two choices: drop the last character of text1 and recurse, or drop the last character of text2 and recurse. Take whichever gives a longer subsequence.

This directly mirrors the mathematical definition of LCS:

  • If text1[i] == text2[j], then LCS(i, j) = 1 + LCS(i-1, j-1)
  • Otherwise, LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))
  • Base case: if either index is less than 0, return 0

Algorithm

  1. Define a recursive function solve(i, j) where i is the current index in text1 and j is the current index in text2.
  2. Base case: if i < 0 or j < 0, return 0 (one string is exhausted).
  3. If text1[i] == text2[j], return 1 + solve(i - 1, j - 1).
  4. Otherwise, return max(solve(i - 1, j), solve(i, j - 1)).
  5. Start the recursion with solve(m - 1, n - 1) where m and n are the lengths of the two strings.

Example Walkthrough

Input:

0
a
1
b
2
c
3
d
4
e
text1
0
a
1
c
2
e
text2

The recursion starts at solve(4, 2), comparing text1="abcde" with text2="ace".

  • solve(4, 2): text1[4]='e' matches text2[2]='e', so return 1 + solve(3, 1).
  • solve(3, 1): text1[3]='d' does not match text2[1]='c', so return max(solve(2, 1), solve(3, 0)).
  • solve(2, 1): text1[2]='c' matches text2[1]='c', so return 1 + solve(1, 0).
  • solve(1, 0): text1[1]='b' does not match text2[0]='a', so return max(solve(0, 0), solve(1, -1)).
  • solve(0, 0): text1[0]='a' matches text2[0]='a', so return 1 + solve(-1, -1) = 1 + 0 = 1.
  • solve(1, -1): j < 0, base case returns 0. So solve(1, 0) = max(1, 0) = 1, and solve(2, 1) = 1 + 1 = 2.
  • Back at solve(3, 1), the other branch solve(3, 0) compares text1[0..3] with text2[0..0]='a' and returns 1 (it finds the single a). So solve(3, 1) = max(2, 1) = 2.
  • Finally solve(4, 2) = 1 + 2 = 3.

The matched characters along the winning path are a, c, and e, giving the LCS "ace" of length 3.

3
result

Code

The recursion recomputes the same subproblems repeatedly. There are only m * n unique (i, j) pairs, but the brute force reaches them through exponentially many paths. Caching each result the first time it is computed removes the redundant work.

Approach 2: Top-Down DP (Memoization)

Intuition

The brute force recursion has correct logic but repeats work. Memoization fixes that: cache the result of solve(i, j) so the same subproblem is never computed twice. Since i ranges from 0 to m-1 and j ranges from 0 to n-1, an m x n table holds every result.

This is the overlapping-subproblems property, one of the two ingredients that make a problem suitable for dynamic programming. The other ingredient, optimal substructure, is already present: the LCS of the full strings is built from the LCS of smaller prefixes.

Algorithm

  1. Create a 2D memo table of size m x n, initialized to -1 (meaning "not computed yet").
  2. Define solve(i, j) with the same logic as Approach 1.
  3. Before computing, check if memo[i][j] != -1. If so, return the cached value.
  4. After computing, store the result in memo[i][j] before returning.
  5. Call solve(m - 1, n - 1).

Example Walkthrough

Input:

0
a
1
b
2
c
3
d
4
e
text1
0
a
1
c
2
e
text2

The same recursion as Approach 1, but now each solve(i, j) stores its result in memo[i][j]. The first call to solve(2, 1) computes and caches the value. Any later call to solve(2, 1) returns instantly from the cache. Instead of exponential calls, we make at most m * n = 15 unique computations, each doing O(1) work.

3
result

Code

The memoized solution reaches O(m * n) time, but the recursion still carries function-call and stack overhead, and on long inputs the call depth can approach m + n. Filling the same table iteratively, row by row, removes the recursion.

Approach 3: Bottom-Up DP (Tabulation)

Intuition

We can build the same DP table iteratively. dp[i][j] represents the LCS length of text1[0..i-1] and text2[0..j-1]. Indices are shifted by 1 so that row 0 and column 0 act as base cases: an empty prefix has LCS 0 with anything, and those cells stay 0.

The table is filled row by row, left to right. The recurrence for dp[i][j] reads dp[i-1][j-1], dp[i-1][j], and dp[i][j-1], all of which are computed before dp[i][j] under this order, so no recursion is needed.

Algorithm

  1. Create a 2D table dp of size (m + 1) x (n + 1), initialized to 0.
  2. For each i from 1 to m and each j from 1 to n:
    • If text1[i-1] == text2[j-1], set dp[i][j] = 1 + dp[i-1][j-1].
    • Otherwise, set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  3. Return dp[m][n].

Example Walkthrough

1Initialize 6x4 dp table with all zeros. Rows=text1 chars, Cols=text2 chars.
0
1
2
3
0
0
0
0
0
1
0
0
0
0
2
0
0
0
0
3
0
0
0
0
4
0
0
0
0
5
0
0
0
0
1/7

Code

Filling row i only reads row i-1 and the cells already written in the current row. The rows above i-1 are never touched again, so keeping the whole table wastes memory. Two rows are enough.

Approach 4: Space-Optimized DP

Intuition

In the recurrence, dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]: two cells from the previous row and one from the current row. Nothing older than the previous row is ever read, so two 1D arrays, prev and curr, are enough. This drops space from O(m * n) to O(n).

One detail matters for correctness. After finishing a row, prev and curr are swapped and curr is reset to zeros. Without the reset, curr would still hold values from two rows back, and the max(prev[j], curr[j-1]) step could read a stale entry instead of treating an unmatched character as contributing nothing.

Algorithm

  1. Create two 1D arrays prev and curr of size n + 1, initialized to 0.
  2. For each row i from 1 to m:
    • For each column j from 1 to n:
      • If text1[i-1] == text2[j-1], set curr[j] = 1 + prev[j-1].
      • Otherwise, set curr[j] = max(prev[j], curr[j-1]).
    • Swap prev and curr, then reset curr to zeros.
  3. Return prev[n].

Example Walkthrough

Running the same input as the earlier approaches, text1="abcde" and text2="ace", the array below shows prev after each row of text1 is processed. Rows for b and d leave prev unchanged because those characters do not appear in text2.

1Initialize prev = [0, 0, 0, 0]. text1 = "abcde" drives the rows; columns 1,2,3 are text2 = "ace".
0
0
1
0
2
0
3
0
1/11

Code