How to understand and solve Longest Common Subsequence (LCS) problem?

Introduction

Hi, I’m Polun. This article will introduce the way of understanding and solving LeetCode 1143. Longest Common Subsequence problem.

This is an entry-level explanation and would also introduce basic dynamic programming knowledge for one who doesn’t quite familiar with it.

Longest Common Subsequence - LeetCode

What is a subsequence?

First, let’s take a look at the definition on the wiki:

In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.

Simple enough. To be a subsequence, two conditions must be satisfied:

1. Create a new sequence from a given one by deleting some or no elements.
2. You shouldn’t change the order of the remaining elements.

Clarify the problem before you dive into it

Now that, in case we already know what a subsequence is, we can move on to the next pieces. What is a common subsequence? The question description already gives a good hint:

A common subsequence of two strings is a subsequence that is common to both strings.

Finally, we can easily read alone and clarify the question again:

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Example 1 :

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Easy peasy.

Brute Force

Here are brute force approach to solve this problem:

1. Find all possible subsequences of text1.
2. Find all possible subsequences of text2.
3. Find all possible common subsequences of 1. and 2.
4. If exits common subsequences, find the longest one and return the length.
5. Otherwise, return 0.

Unfortunately, the first step will lead to exponential time complexity, which is horrible and will make test cases time out.

Wait a minute, is this a Dynamic Programming problem?

When we take more look at above Example 1 by the naked eye. We can observe that we continuously look back and forth between two strings to compare each string element from left to right and meanwhile subconsciously memorize the current longest common subsequences, and finally stop at the last element.

It’s a worth taking sign that we may encounter a “Two Pointer + Dynamic Programing” problem.

If you are not familiar with Dynamic Programing or DP, there is a really good explanation on LeetCode Explore. And as mentioned, DP problems usually have two common characteristics:

1. The problem can be broken down into “overlapping subproblems”.

2. The problem has an “optimal substructure”.

Since the question is asking for “longest” common subsequences and we keep memorizing the current version of the answer in our mind after checking every element, These characteristics are pretty consistent.

Finding patterns

The next question is, how the original problem can break it down into smaller subproblems?

On other hand, how the future decisions depend on earlier decisions?

Let’s keep working on the same Example:

text1 = "abcede"
text2 = "ace"

As mentioned above, we will continuously compare one element from text1 to another single element from text2 each time, without changing the order, until we meet the end.

Therefore, let’s take a look at the latest element comparison from both text1 and text2, which is the end case of the whole process. At this moment, the last element from text1 is "e" and the last element from text1 is also "e". We can tell that the longest common subsequences (LCS) of text1 and text2 have at least a length of 1.

LCS("abcde", "ace") = 1 + Previous version of LCS subproblem

Since we identified a certain part, the problem has broken into smaller uncertain pieces, which is a subproblem. Both "e" elements from two given strings are classified as part of LCS, we can remove them from the original problem. Therefore, the new subproblem will become the length of LCS without the common element "e", which is LCS("abcd", "ac").

LCS("abcde", "ace") = 1 + LCS("abcd", "ac")

Let’s do the latest element comparison process again for LCS("abcd", "ac"). The latest element from both strings is "d" and "c" respectively, which is no match. This means that the comparison at this point has no contribution at all. Our answer may equal some certain points of the previous version of LCS.

So let’s find out what possible paths can get to this point. As we mentioned before in the “naked eye approach”, we tend to memorize the current LCS from the starting point of the subsequences until the end. There are two possible closest points during that process:

1. LCS for input sequences "abcd" and "a" is "a"of length 1.
2. LCS for input sequences "abc" and "ac" is "ac"of length 2.

The larger one is the current version of LCS at this moment.

LCS("abcd", "ac") = Max(LCS("abcd", "a"), LCS("abc", "ac"))

Awesome. Time to recap our discovers currently:

* Given two input sequences s1 and s2.
* The longest common subsequence (LCS) is expressed as: 
  LCS(s1, s2)
* The last elements of the s1 and s2 are represented by e1 and e2  respectively, and the rest are represented by sub1 and sub2, so the S1 and S2 can be represented as follows:
  s1 = sub1 + e1
  s2 = sub2 + e2
* The problem can be reduced into follow relation:
  if e1 is equal to e2:
  
    LCS(s1, s2) = 1 + LCS(sub1, sub2)
  otherwise:
    LCS(s1, s2) = Max(LCS(s1, sub2), LCS(sub1, s2))
* When s1 or s2 is an empty set, the LCS is also an empty set.

There are two ways to implement a DP algorithm: Top-down and Bottom-up. Both of them follow the same rules of state-changing relations but approach them in different directions. The major difference is, that when we encounter the same subproblem, the top-down approach will stick to it and breaks it into smaller subproblems, until it reaches the base cases, in a recursively way. In the bottom-up approach, we calculate the answer from the base case and store it in a table or somewhere, finally to the destination. So at every point of state transition, we directly access the calculated states from the table itself and figure out a new state, and so on.

Top-down

For the whole process by top-down approach would be like this:

top-down approach

The subproblems marked as an orange background such as LCS("abcd", "") and LCS("", "") would be the base case of recursive, which would return 0. Since it’s no way to exist any common subsequences with an empty string from any sting.

You may notice that some same subproblem marked as green underline appears more than once, such as LCS("ab", "a"). It means we need to calculate LCS("ab", "a") two times, this might not seem like a big deal, but imagine when the input sequence is really big that would be an issue. The more efficient way is memoizing the result of a function call. Therefore, we can just refer to the value we already calculated instead of having to go through the entire tree again.

Bottom-up

Let’s talk about the bottom-up method. Since we want to calculate the final value base on the previous values, why don’t we make a table and record every state-changing point from the ground up? This is why the bottom-up approach is also called tabulation, and in my opinion, this method would be more efficient and reasonable for the LCS problem.

First, fill up all base cases for comparing any strings with an empty string:

Base cases for the bottom-up approach

For cells whose corresponding row and column element match, the answer should refer to the top-left cell value plus 1. For example LCS("a", "a") = 1 + LCS("", "").

For cells whose corresponding row and column elements don’t match, the answer should refer to the maximum value of the top or left cell. For example LCS("ac", "a") = Max(LCS("ac", ""), LCS("a", "a")).

Here is the final state transition result of the tabulation method from the top-left corner to the right-bottom destination:

Bottom-up approach result

Finally, after tons of mind settings, here comes the code:

The time complexity of the bottom-up approach is O(m * n) and space complexity is also O(m * n), m refers to the length of text1 and n refers to the length of text2.

Thanks for watching. I’m Polun, see you guys next time :).

Reference

How to solve a Dynamic Programming Problem ? - GeeksforGeeks

Tabulation vs Memoization - GeeksforGeeks

HackerRank: Common Child (JavaScript)

最長共同子序列 (Longest Common Subsequence; LCS) - Part 1

[Leetcode 筆記] 1143. Longest Common Subsequence