leetExpert
Practice

Longest Common Subsequence

Module 24 · Dynamic Programming

Problem

Given two strings text1 and text2, return the length of their longest common subsequence (a subsequence need not be contiguous, but must preserve relative order) — or 0 if they share none. (LeetCode 1143.)

Examples

Example 1

Inputtext1 = "abcde", text2 = "ace"Output3

Explanation. "ace" is a subsequence of both

Example 2

Inputtext1 = "abc", text2 = "def"Output0

Explanation. no common subsequence at all

Constraints

1 ≤ text1.length, text2.length ≤ 1000.

Attempt it first

This is the canonical two-sequence 2D DP from the 2D DP Patterns concept lesson — dp[i][j] is NOT a grid position, it's a pair of independent progress counters, one into each string. Before opening anything, define dp[i][j] = the LCS length considering only the first i characters of text1 and the first j characters of text2, and work out the TWO cases the recurrence must handle: what happens when text1[i-1] == text2[j-1] (the two strings' NEXT characters happen to match), and what happens when they don't.