Find the length of the longest common subsequence (LCS) of two strings.

How to think about it

Recognise the pattern

The signal is “longest / shortest subsequence or edit distance between two sequences.” Any time you have two strings (or arrays) and need to align them while making choices (match, skip left, skip right), think 2-D DP. The classic family includes LCS, Edit Distance, and Longest Common Substring. All share the same table structure — only the recurrence changes.

Define the DP

• State: dp[i][j] = length of LCS of text1[:i] and text2[:j].
• Recurrence:
  • If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
  • Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• Base cases: dp[0][j] = dp[i][0] = 0 (empty string has LCS 0 with anything).

Build the approach step by step

Brute force generates all 2^m subsequences of text1 and checks each against text2 — exponential.

The DP insight: when text1[i-1] == text2[j-1], both strings end in the same character, so we extend the LCS of the prefixes without that character. When they differ, we take the better option of ignoring the last character of either string.

Walk through text1="abcde", text2="ace":

     ""  a  c  e
  ""  0  0  0  0
  a   0  1  1  1
  b   0  1  1  1
  c   0  1  2  2
  d   0  1  2  2
  e   0  1  2  3   <- answer

Complexity

• Time — O(m × n): fill every cell in the table once.
• Space — O(m × n): the full table. Optimisable to O(min(m, n)) by keeping only two rows at a time, since each row only looks at the row above.

Traps and variants