HackerRank: Common Child (Longest Common Subsequence) — JavaScript

Photo by Amador Loureiro on Unsplash

The Common Child challenge on HackerRank is the nickname for the classic Longest Common Subsequence (LCS) problem. Here is a link to this challenge:

Common Child | HackerRank

A subsequence is a new string that is derived from an original string with 0 or more characters deleted, without altering the relative order of the characters that remain in the string.

Our task with this problem is to find and return the length of the longest possible subsequence that is common to 2 given strings. If no common subsequence exists, then return 0.

There are several different approaches to solving this problem. The brute force approach would involve generating every possible subsequence for each string and finding the longest common one. This would mean exponential time complexity, and your tests would surely time out, as the constraints for string length go to 5000 in this challenge.

Find the common subsequence of these two sets of letters using visual inspection:

a b d e f

a c d f

You probably noticed that you were shuttling back and forth between the two strings and retaining what was common, eventually getting to the end. So there were both the elements of comparison and retention. At each moment you were dealing with a focused subproblem, the solution of which you attached to what you had already established.

In essence, you were performing dynamic programming, whether you knew it or not! With longer strings, you might have jotted down your progress and kept your pencil points on where you were in each string to keep your place.

When you hear the word “subproblem,” you might (or might not!) think of recursion, and recursion is certainly a way to solve this challenge. I’ve elected to use a table approach to keep track of my progress because I am a visual learner, but it is instructive to look at the actual subproblems to delineate the decisions that are made with each comparison.

To understand these subproblems, we are going to start comparing from the end of the strings. Why? Well, because every decision we make regarding the current length of the subsequence relies on what came before.

a b d e f

a c d f

Without seeing what came before, let’s assume we already know the length of the LCS when it’s time to consider the two “f”s. What we can say for certain is that LCS = 1 + LCS, since the common “f”s can be added to the current common sequence.

Working backward:

a b d e

a c d

The”e” and “d” do not match, so what do we do? At this point, we need to figure out the LCS length for “abd” and “acd”; and then the LCS length for “abde” and “ac”. In other words, lop off the last letter of one and compare it to the other string, finding the LCS length. Then do it the other way around for the other pair. In this case, it’s 2 for the former, 1 for the latter. So, since we are interested in the longest, we will take the value of 2. You can go back further until you get to the base case of empty strings, but at this point, we can visually confirm that 2 is correct. And continuing, adding the f’s back, our final LCS has the length of 3.

LCS(“abdef”, “acdf”) is 3

Since we’ve sketched out the decision process for each subproblem, we can fill out our dynamic programming table.

I’ve added the base case of empty strings since we will need to have some 0’s to start running our subproblems. Now we can start comparing the strings from the beginning.

Comparing the empty strings or a string of any length with an empty string, will give us 0. So our LCS is 0 when we start to compare the letters.

Comparisons:

“a” with “a” — look at the cell diagonally to the left. This cell represents the string when both a’s are removed. So we add 1 and fill in the cell:

“a” with “ab” (the strings are cumulative across the columns) — compare the cell to the left with the cell above. You are comparing the values at “a” and “a” with “” and “ab”, the result of looking at the prior LCS values. Enter the max of 1 and 0, which is 1:

In this fashion you will fill out the table and the bottom right-hand corner will hold the final LCS.

So now we just need to pseudocode the subproblems:

1. Initialize a two-dimensional array lcs with 0’s, with dimensions s1.length + 1 and s2.length + 1. The extra column and row account for starting with empty strings.
2. Iterate through lcs[i][j].
3. Compare each the row letter with each column letter.
4. If they are equal, add 1 to the value found in lcs[i -1][j — 1].
5. Else, take the max of lcs[i — 1][j](the cell above) and lcs[i][j — 1](the cell to the left)
6. Continue until the table is complete.
7. Return lcs[s1.length][s2.length].

And the final code in JavaScript:

This coding challenge was the first I ever encountered using the table technique of dynamic programming. It took me a while to understand the reasoning behind the algorithm and apply it to the table, but I feel like the process has improved my ability to take something that seems complicated to keep track of and boil it down to very basic subproblems that I can wrap my head around. With a little tweaking of this code, the next challenge could be to return the actual resulting subsequence. Try it. I know I will!

Happy coding!