Longest common subsequence - DSA Practice

Given two strings str1 and str2, find the length of their longest common subsequence.

A subsequence is a sequence that appears in the same relative order but not necessarily contiguous and a common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: str1 = "bdefg", str2 = "bfg"

Output: 3

Explanation: The longest common subsequence is "bfg", which has a length of 3.

Example 2:

Input: str1 = "mnop", str2 = "mnq"

Output: 2

Explanation: The longest common subsequence is "mn", which has a length of 2.

Now Your Turn!

Pick the correct output for the given input

Input: str1 = "abc", str2 = "dafb"

2013

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

n=str1.length
m=str2.length
1<= n, m <=10³
str1 and str2 are in lowercase alphabet

25. Longest common subsequence

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Hint 1

Hint 2

Topic Tags

Patterns

Frequently Occurring Doubts

Why do we need a 2D DP table instead of a 1D DP array?

How can we optimize space from O(n × m) to O(min(n, m))?

Interview Follow-up Questions

What if str1 and str2 were large, but had small alphabets?

How can we optimize this problem to O(n log m) instead of O(n × m)?

Fun Facts

Fun Fact 1

Fun Fact 2