Common child solution

This is one of the medium difficulty problems in the string manipulation section of Hackerrank’s interview preparation kit problem set. Link here.

The problem states that given two strings s1 and s2 you need to find the largest common child string. A child string is a sequence of characters that follows the same order of the original string but may or may not contain all the characters of the string. This is the longest common subsequence problem.

Solution

We need to use dynamic programming to solve this question. The recurrence relation in this dp problem is the following:

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

To illustrate this the longest common subsequence of LCS(SA , HARR) will be 1+ LCS(S, HAR) if A = R otherwise Max(LCS(S, HARR), LCS(SA, HAR) ).
So if the last characters are equal we will extend on the LCS of the strings without those characters otherwise we choose the longest removing either character. With this recurrence relation we can easily implement the dp solution in a bottom up fashion.

Code

Github link with complete code

static int T[5001][5001];
int commonChild(string s1, string s2) {
    int m = s1.size();
    int n = s2.size();
    
    for(int i = 0; i <= m; i++ ){
        for(int j = 0; j <= n; j++ ){
            if(i == 0 || j == 0){
                T[i][j] = 0;
            }else if(s1[i-1]==s2[j-1]){
                T[i][j] = 1+T[i-1][j-1];
            }else{
                T[i][j] = max(T[i][j-1], T[i-1][j]);
            }
        }
    }
    
    return T[m][n];
    
}