While going through HackerRank's Interview Preparation Kit I came across a problem that was exceptionally challenging. The problem was called Common Child. When I realized that I wasn't going to figure it out on my own, I decided to check the discussion section to look for tips. I noticed many of the comments were mentioning something about dynamic programming. After taking some time to learn about dynamic programming and how it can be implemented to coding, I came back to this challenge and managed to figure it out. In this post I will discuss the Common Child problem and how we can use dynamic programming to solve it.
Common Child is a variety of a more common problem, the Longest Common Subsequence(LCS) problem. In this problem we must compare two strings and find the longest child(or subsequence) between them. Subsequences do not need to be consecutive, so it's not exactly the same as finding the longest substring between two strings. For instance, if we have strings "ABCD" and "ABDC", the longest common substring would be "AB" but the longest subsequence would be "ABC" or "ABD."
The most effective way to solve this problem is by making use of dynamic programming. Dynamic programming is a method for solving problems by breaking a problem down into smaller problems and saving those problems' solutions for later use. We can use dynamic programming to save time for problems that have overlapping subproblems, or in other words, subproblems that must be solved more than once.
In Common Child, we can break down the problem of finding the longest common child of two strings by finding the longest common child of two smaller strings. For example, to find the LCS of "ABCD" and "ABDC" we can first look at the strings "AB" and "AB". We know that the LCS of those strings is "AB" because they are the same. Next, we could compare "ABC" to "ABD" and because "C" !== "D" our answer has not changed. The LCS is still "AB". One step further, we can compare "ABCD" to "ABD". Here we find that the last character in both strings is "D" so we can add that to our previous answer. The LCS is now "ABD". Finally, we compare the full strings "ABCD" and "ABDC" and because the final letter "C" does not equal "D" our answer is not changed. The final answer is "ABD". Alternatively, we could have compared "ABDC" to "ABC" and found "ABC" as our answer.
Now getting into the real solution, to employ dynamic programming we need to use either a table or a memo to save our subproblems' solutions. For my solution, I chose to use a table. In Common Child, we are given two strings, s1 and s2. The columns of our table represent the characters in s1 and the rows represent the characters in s2. Each cell will contain the length of the LCS between the substrings that end with that character in the row/column. To illustrate, for the strings "ABCD" and "ABDC" the cell in row 2 and column 2 would compare the strings "AB" and "AB" and contain the number 2.
To fill out our table, we will use a nested loop to iterate over every character in s2 for each character in s1. Then we check if the characters for that row and column are the same. If they are, the answer to our subproblem is 1 + the answer 1 column up and 1 row left in our table. If not, the answer to the problem is the answer in the cell one column up OR one row to the left, whichever number is higher. At the end, our final answer is the last cell of our table.
Here is my solution in JavaScript.
function commonChild(s1, s2) {
//initializing the table
//The first row and column of our table must contain all 0's for our solution to work.
const table = [new Array(s2.length+1).fill(0)]
for(let i=0; i<s1.length;i++) table.push([0])
//iterating over the strings and filling out each row of our table
for(let i=1;i<s1.length+1;i++){
for(let j=1;j<s2.length+1;j++){
if(s1[i-1] === s2[j-1]) table[i][j] = table[i-1][j-1] + 1
else table[i][j] = Math.max(table[i-1][j],table[i][j-1])
}
}
//The last cell of our table contains our answer
return table[s1.length][s2.length]
}
Top comments (0)