Longest Common Subsequence

Asked byAmazonDoorDashBloombergKarat

Problem

Given two strings, return the length of their longest common subsequence — the longest sequence of characters that appears, in order but not necessarily contiguously, in both strings. Return 0 if no common subsequence exists.

Examples

Example 1

Input:text1 = "abcde", text2 = "ace"

Output:3

The subsequence is "ace".

Example 2

Input:text1 = "abc", text2 = "def"

Output:0

Constraints

1 <= text1.length, text2.length <= 1000

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the 2-D Dynamic Programming pattern

The same DP idea as 1-D, but the state depends on two indices — often two positions in a grid, or a position in each of two sequences being compared.

Look for this pattern when

You're comparing two sequences (finding a longest common subsequence, edit distance).
You're computing paths or optimal values across a 2-D grid.

Read the full 2-D Dynamic Programming guide →

Video walkthroughs

Original problem on LeetCode ↗