Common Child — HackerRank Medium — Dynamic Programming

Link to problem

When dealing with things such as two strings and such, dynamic programming is the easiest approach to use and usually the fastest as well. Since, we are given two strings and are asked to find the longest child of both, dynamic programming is a very efficient approach to solving this.

Before we begin, if these two characteristics are found in a problem, it usually suggests us that dynamic programming can solve the problem:

1. Overlapping subproblems
2. Optimal Substructure Property

Moving on to solve the problem, we need to decide when to add the count and when to just take the maximum.

If not equal, we take the maximum of top or left.

Why?

This shows that deleting having the respective elements in each list or not does not matter at the current index. Because we dont have a match.

Now if there is a match, as below, we take the diagonal and add 1 to it. Why?

This shows that this match will increase the length of our longest child by one.

As we move on doing the same for all the elements in both the lists, the last element of our dynamic programming array is our answer.

This approach makes sure that, the characters in the string are in subsequent order. This is also a requirement of the problem.

This is achieved by the fact that we are taking the maximum of top and left. Which causes the values to reset for each index and start from 0 as seen in the picture demonstrating our dynamic programming array in the left.

To code:

// An array with word length + 1 to accommodate taking 0 elements from each array.
int dp [][] = new int [s1.length()+1] [s2.length()+1]; 

Then,

for(int i = 1; i <= s1.length(); i ++){
   for(int j = 1; j <= s1.length(); j++){
      if(s1.charAt(i-1) == s2.charAt(j-1)){
         dp[i][j] = dp[i-1][j-1] + 1; // If equal
      }else{
         dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // Not equal
      }
   }
}
// Then simply return the last elemet
return dp[s1.length()][s2.length()];

Here is the full code

Thank you! Please hit the like button if it helped you.