Longest Common Subsequence

Medium⊞ 2D Dynamic ProgrammingStringDynamic Programming

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

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

Pattern Recognition & Intuition

Why this is a 2D Dynamic Programming problem

⊞

2D Dynamic Programming

Build solutions for a grid of sub-problems — rows and columns of choices.

2D DP stores answers in a 2D table dp[i][j], where i and j typically represent two independent dimensions — like two strings, a grid position, or (item, remaining-capacity) in knapsack. The final answer is usually dp[m][n] built from smaller sub-tables.

MENTAL MODEL

Draw the 2D table first. Label the axes. Then figure out what dp[i][j] means and which neighboring cells it depends on.

INTUITION

Picture an edit-distance problem: to transform "cat" into "car" you can insert, delete, or replace. Each decision combines the results of transforming smaller prefixes. The 2D table captures every possible prefix-pair in one grid — and each cell is filled in O(1) using the three cells above-left, above, and left.

SIGNALS — WHEN TO USE THIS PATTERN

Two sequences/strings: "longest common subsequence", "edit distance", "interleaving strings"
Grid path problems: "unique paths", "minimum path sum", "dungeon game"
2D state: (index in string 1, index in string 2) or (row, column)
"Subsequence" (not subarray) — subsequences allow skipping
Knapsack variants with two dimensions (weight + item index)

Approaches & Trade-offs

From brute force to optimal — understand every step of the journey

BRUTE FORCE

Brute Force

⏱ O(2^(m+n)) — exponential branches💾 O(m+n) recursion depth

✦ OPTIMAL

Optimal

⏱ O(m × n) — fill every cell once💾 O(m × n); optimizable to O(min(m,n)) using rolling rows

Fill a 2D table row by row. Each cell dp[i][j] is computed from previously filled cells in O(1).

ALGORITHM STEPS

Define dp[i][j]: answer for sub-problems using first i chars of s1, first j chars of s2
Initialize the table: dp[0][j] = 0, dp[i][0] = 0 (base cases)
Double loop: for i in 1..m, for j in 1..n
Fill dp[i][j] using the recurrence: match → dp[i-1][j-1]+1; no match → max(dp[i-1][j], dp[i][j-1])
Return dp[m][n]

TIME

O(m × n) — fill every cell once

SPACE

O(m × n); optimizable to O(min(m,n)) using rolling rows

Space optimization: only need the current and previous rows.

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[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]

Key Insight & Common Pitfalls

THE "AHA" MOMENT

The hardest part is defining what dp[i][j] represents. Write it as an English sentence before touching code. For string problems, i and j almost always represent prefix lengths (not indices). For grid problems, dp[i][j] represents the answer reaching cell (i, j). Once you have the definition, ask: "what choice do I make at (i, j), and what prior state does each choice depend on?"

COMMON MISTAKES

✕Confusing "indices" with "prefix lengths" — dp[i][j] usually refers to first i chars, not index i
✕Not initializing the first row and column (base cases for empty prefix)
✕Wrong traversal order — always fill in the direction your dependencies point
✕Forgetting to handle the "diagonal" case (character match) separately

PRO TIPS

›Draw the table on paper, fill 2-3 cells manually — confirms your recurrence before coding
›Space optimization: dp[i][j] depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1] → use two 1D arrays
›For grid paths (no skipping), check if 1D rolling array suffices by tracing dependencies
›"Palindrome" problems often reframe as LCS(s, reverse(s)) — a 2D DP trick

Interactive Visualizer

Building ⊞ 2D Dynamic Programming Visualization

Generating visualization…