86. Longest Common Subsequence

PRO

Medium

Topics

Companies

Hint

Understand Before Coding

Step 1 / 44

Speed: 1.0x

LCS Table (Bottom-Up)

	a 0	c 1	e 2	∅ 3
a 0	0	0	0	0
b 1	0	0	0	0
c 2	0	0	0	0
d 3	0	0	0	0
e 4	0	0	0	0
∅	0	0	0	0

Step Explanation

Initialize a 2D array dp of size (m+1) x (n+1) with all values set to 0. dp[i][j] will store the LCS of text1[i:] and text2[j:].

Why this works

LCS can be solved by comparing characters from the end of both strings.

If characters match, the LCS length increases by 1 plus the LCS of the remaining suffixes: `1 + dp[i+1][j+1]`.

If they mismatch, the LCS length is the maximum value found by either skipping `text1[i]` or `text2[j]`: `max(dp[i][j+1], dp[i+1][j])`.

Variables

i-

j-

text1[i]-

text2[j]-

dp[i][j]0

Loading visualization...

Visualize This Problem

Open Visualizer

Draw Your Approach

Draw

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:

•
•

Time Complexity

O(m × n)

Space Complexity

O(m × n)

86. Longest Common Subsequence

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

86. Longest Common Subsequence

Understand Before Coding

LCS Table (Bottom-Up)

Step Explanation

Why this works

Variables

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

LCS Table (Bottom-Up)

Step Explanation

Why this works

Variables