# Challenge: Longest Common Subsequence

In this lesson, we will look at another classic dynamic programming problem: the longest common subsequence problem.

## We'll cover the following

## Problem statement

Given two strings, find the length of the longest common subsequence between them. A common subsequence in a pair of strings is a sequence that follows the same order of characters, but the sequence does not necessarily have to be contiguous. For example, two strings `two`

and `too`

have a common subsequence of `to`

. Even though `to`

does not appear contiguously in `two`

, the order of characters is still preserved, i.e., `o`

follows `t`

. While these strings had smaller subsequences as well, such as `t`

and `o`

, in the context of this problem, we are only interested in finding the length of the longest subsequence.

## Input

Your algorithm will take two strings, i.e., `str1`

and `str2`

, as input. Strings can be of variable length, even empty too.

```
str1 = "two"
str2 = "too"
```

## Output

Your algorithm should return an integer representing the length of the longest common subsequence.

```
LCS("two", "too") = 2
```

## Problem statement

You have already solved a similar problem of the longest common substring in the previous chapter. This problem is slightly different because we are finding subsequence instead of substring here. Think about a simple recursive solution first and then build on that to write a dynamic programming solution. Best of luck!

Get hands-on with 1200+ tech skills courses.