# Hands-on: Longest Common Subsequence (with progressive 'hint-by-hint' solution)

July 03, 2018

Another 2D dynamic programming problem, this time with strings. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

# Problem Statement

Given two strings, find a *longest subsequence* common to both strings. Note that unlike substrings, subsequences are

**not**required to be a consecutive section of the original strings.

Your solution should have run-time O($nm$).

Note: There may be multiple subsequences of the same length. You are required to calculate *any* subsequence of the maximum possible length.

# Examples

**Example 1:**

```
String 1: ABBBAABB
String 2: ABBABA
```

Answer: “ABBBA” (length=5)

**Example 2:**

```
String 1: ABACCAA
String 2: BAACABAC
```

Answer: “BACAA” (length=5)

**Example 3:**

```
String 1: DBCCBDDACD
String 2: CBDCB
```

Answer: “CBDC” (length=4)

# Submitting your solution

Once you are confidant of your solution, take the quiz! It will provide you with some inputs to run your code on.

# Progressive ‘hint-by-hint’ solution

Only look at the hints if you can’t solve the problem for **at-least 20-minutes**. Read **only one hint** that you could not figure out on your own. Then spend **at-least 20-minutes** trying to solve the problem again.

Hint 1 (dp state):

lcs(i, j) = *length* of longest common subsequence of string1[0 … i] and string2[0 … j]

Hint 2 (recursion):

There are two cases: `string1[i] == string2[j]`

or `string1[i] != string2[j]`

.

Hint 3:

The `string1[i] == string2[j]`

case is left for you. If `string1[i] != string2[j]`

, then the LCS either does not include `string1[i]`

or does not include `string2[j]`

. Hence, lcs(i, j) = max(lcs(i-1, j), lcs(i, j-1)).

Hint 4 (constructing the actual subsequence):

You’ll need to define previous(i, j) to remember the *path* you took from (0, 0) to (i, j). previous(i, j) should be one of (i-1, j), or (i, j-1) or (i-1, j-1).

# Full solution

The solution for this assignment is included at the end of the quiz.