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.

The key observation is that 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. This recursive structure is what makes dynamic programming the right tool here.

Key Constraints:

1 <= text1.length, text2.length <= 1000 -> Both strings can be up to 1000 characters. With m and n up to 1000, an O(m * n) solution means about 1 million operations, which is very comfortable. An O(2^n) brute force would be astronomically slow.
text1 and text2 consist of only lowercase English characters. -> No special character handling needed. Only 26 possible characters.

Approach 1: Brute Force (Recursion)

Intuition

The most natural way to think about this problem is recursively. Start from the end of both strings and compare characters. If the last characters match, they are part of the LCS, so we add 1 and recurse on the remaining prefixes. If they don't match, we have two choices: drop the last character of text1 and recurse, or drop the last character of text2 and recurse. We 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

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

Example Walkthrough

Input:

text1

text2

The recursion starts at solve(4, 2). Since text1[4]='e' matches text2[2]='e', we get 1 + solve(3, 1). At solve(3, 1), text1[3]='d' does not match text2[1]='c', so we branch into solve(2, 1) and solve(3, 0). At solve(2, 1), text1[2]='c' matches text2[1]='c', giving 1 + solve(1, 0). This pattern continues until we reach the base cases, ultimately returning 3.

result

Code

Complexity Analysis

Time Complexity: O(2^(m+n)). At each step when characters don't match, we branch into two recursive calls. The branching factor of 2 leads to exponential growth.
Space Complexity: O(m + n). The recursion stack can go at most m + n levels deep.

The recursion recomputes the same subproblems over and over. The number of unique (i, j) pairs is only m * n, but the brute force explores exponentially many paths. What if we cached each result the first time we compute it?

Approach 2: Top-Down DP (Memoization)

Intuition

The brute force recursion has the right logic, it just does too much redundant work. The fix is memoization: cache the result of solve(i, j) so we never compute the same subproblem twice. Since i ranges from 0 to m-1 and j ranges from 0 to n-1, we need an m x n table to store results.

This is a classic example of overlapping subproblems, 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 can be built from the LCS of smaller prefixes.

Algorithm

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

Example Walkthrough

Input:

text1

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.

result

Code

Complexity Analysis

Time Complexity: O(m n). Each unique subproblem (i, j) is solved exactly once, and there are m n such subproblems. Each does O(1) work.
Space Complexity: O(m n). The memo table stores m n entries, plus O(m + n) for the recursion stack.

The memoized solution has the right time complexity, but the recursion still adds stack overhead. What if we filled the table iteratively instead, row by row, eliminating recursion entirely?

Approach 3: Bottom-Up DP (Tabulation)

Intuition

Instead of recursion with memoization, we can build the DP table iteratively. The idea is the same: dp[i][j] represents the LCS length of text1[0..i-1] and text2[0..j-1]. We shift indices by 1 so that dp[0][...] and dp[...][0] serve as the base cases (empty string has LCS 0 with anything).

We fill the table row by row, left to right. When we compute dp[i][j], we already have dp[i-1][j-1], dp[i-1][j], and dp[i][j-1] available. This eliminates recursion entirely and gives us a clean iterative solution.

Why does this work?

The bottom-up approach fills the table in a topological order of the subproblem dependency graph. When we process dp[i][j], rows 0 through i-1 are fully complete, and columns 0 through j-1 in the current row are also complete. So all three dependencies are available.

The recurrence directly encodes the optimal substructure: if the current characters match, we extend the LCS by 1. If they don't, the LCS must come from one of the two shorter prefixes, and we pick the better one.

Algorithm

Create a 2D table dp of size (m + 1) x (n + 1), initialized to 0.
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]).

Return dp[m][n].

Example Walkthrough

1Initialize 6x4 dp table with all zeros. Rows=text1 chars, Cols=text2 chars.

1/7

Code

Complexity Analysis

Time Complexity: O(m n). We fill each of the (m + 1) (n + 1) cells exactly once, doing O(1) work per cell.
Space Complexity: O(m n). The 2D DP table uses (m + 1) (n + 1) space.

The full 2D table works, but when filling row i, we only ever look at row i-1 and the current row. What if we only kept two rows in memory at a time?

Approach 4: Space-Optimized DP

Intuition

Looking at the recurrence, dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. That means we only need the previous row and the current row. We can reduce space from O(m * n) to O(n) by using two 1D arrays.

Algorithm

Create two 1D arrays prev and curr of size n + 1, initialized to 0.
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.

Return prev[n].

Example Walkthrough

1Initialize: prev = [0, 0, 0, 0]. Columns represent text2 = "abc".

1/7

Code

Complexity Analysis

Time Complexity: O(m * n). Same as Approach 3, we still fill every cell exactly once.
Space Complexity: O(n). We only store two arrays of size n + 1 instead of the full 2D table.

Longest Common Subsequence

Understanding the Problem

Key Constraints:

Approach 1: Brute Force (Recursion)

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Top-Down DP (Memoization)

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Bottom-Up DP (Tabulation)

Intuition

Algorithm

Example Walkthrough

Code

Approach 4: Space-Optimized DP

Intuition

Algorithm

Example Walkthrough

Code

Get Premium