HackerRank Common Child Problem Solution

In this post, we will solve HackerRank Common Child Problem Solution.

A string is said to be a child of a another string if it can be formed by deleting 0 or more characters from the other string. Letters cannot be rearranged. Given two strings of equal length, what’s the longest string that can be constructed such that it is a child of both?
Example
s1 = ‘ABCD’
s2= ’ABDC
These strings have two children with maximum length 3, ABC and ABD. They can be formed by eliminating either the D or C from both strings. Return 3.

Function Description

Complete the commonChild function in the editor below.

commonChild has the following parameter(s):

string s1: a string
string s2: another string

Returns

int: the length of the longest string which is a common child of the input strings

Input Format

There are two lines, each with a string, s1 and s2.

Sample Input

HARRY
SALLY

Sample Output

Explanation
The longest string that can be formed by deleting zero or more characters from HARRY and SALLY is AY, whose length is 2.

Sample Input 1

AA
BB

Sample Output 1

Explanation 1
AA and BB have no characters in common and hence the output is 0.

Sample Input 2

SHINCHAN
NOHARAAA

Sample Output 2

Explanation 2
The longest string that can be formed between SHINCHAN and NOHARAAA while maintaining the order is NHA.

Sample Input 3

ABCDEF
FBDAMN

Sample Output 3

Explanation 3
BD is the longest child of the given strings.

Table of Contents

Common Child C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int process(char *str1,int i1,char *str2,int i2,int **dp);

int main(){
  char str1[5001],str2[5002];
  int len,**dp,i,j;
  scanf("%s%s",str1,str2);
  len=strlen(str1);
  dp=(int**)malloc(len*sizeof(int*));
  for(i=0;i<len;i++)
    dp[i]=(int*)malloc(len*sizeof(int));
  for(i=0;i<len;i++)
    for(j=0;j<len;j++)
      dp[i][j]=-1;
  printf("%d",process(str1,len-1,str2,len-1,dp));
  return 0;
}
int process(char *str1,int i1,char *str2,int i2,int **dp){
  int len1,len2;
  if(i1==-1 || i2==-1)
    return 0;
  if(dp[i1][i2]!=-1)
    return dp[i1][i2];
  if(str1[i1]==str2[i2])
    dp[i1][i2]=process(str1,i1-1,str2,i2-1,dp)+1;
  else{
    len1=process(str1,i1-1,str2,i2,dp);
    len2=process(str1,i1,str2,i2-1,dp);
    dp[i1][i2]=(len1>len2)?len1:len2;
  }
  return dp[i1][i2];
}

Common Child C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int dp[5001][5001];

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    string s1, s2;
    cin >> s1 >> s2;
    
    int lg = 0;
    for(int i = 0; i < s1.size(); ++i) {
        for(int j = 0; j < s2.size(); ++j) {
            if (s1[i] == s2[j]) {
                dp[i+1][j+1] = dp[i][j] + 1;
                lg = max(lg, dp[i+1][j+1]);
            } else {
                dp[i+1][j+1] = max(max(dp[i][j], dp[i+1][j]), dp[i][j+1]);
            }
        }
    }
    
    cout << lg << endl;
    
    return 0;
}

Common Child C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    
    static int LCSLength(string str1, string str2)
    {
        if (string.IsNullOrEmpty(str1) || string.IsNullOrEmpty(str2))
            return 0;
        
        if (str1[0] == str2[0])
            return 1 + LCSLength(str1.Substring(1), str2.Substring(1));
        else
        {
            int len1 = LCSLength(str1, str2.Substring(1));
            int len2 = LCSLength(str1.Substring(1), str2);
            return Math.Max(len1, len2);
        }
    }
    
    static int Solve(string str1, string str2)
    {
        return LCSLength(str1, str2);
    }

    static int Solve2(string str1, string str2)
    {
        var L = new int[str1.Length + 1, str2.Length + 1];
        for (int i = str1.Length - 1; i >= 0; --i)
        {
            for (int j = str2.Length - 1; j >= 0; --j)
            {
                if (str1[i] == str2[j])
                {
                    L[i,j] = 1 + L[i+1, j+1];
                }
                else
                {
                    L[i,j] = Math.Max(L[i, j+1], L[i+1, j]);
                }
            }
        }
        
        return L[0,0];
    }
    
    
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        string str1 = Console.ReadLine();
        string str2 = Console.ReadLine();
        
        Console.WriteLine(Solve2(str1, str2));
    }
}

Common Child Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'commonChild' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. STRING s1
     *  2. STRING s2
     */

    public static int commonChild(String a, String b){
        int[][] C = new int[a.length()+1][b.length()+1];

        for (int i = 0; i < a.length(); i++) {
            for (int j = 0; j < b.length(); j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    C[i+1][j+1] = C[i][j] + 1;
                } else {
                    C[i+1][j+1] = Math.max(C[i+1][j], C[i][j+1]);
                }
            }
        }
        for (int i = 0; i < a.length(); i++) {
        }

        return C[a.length()][b.length()];
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String s1 = bufferedReader.readLine();

        String s2 = bufferedReader.readLine();

        int result = Result.commonChild(s1, s2);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Common Child JavaScript Solution

function processData(input) {
    input = input.split('\n');
    var X = input[0];
    var Y = input[1];
    var m = X.length;
    var n = Y.length;
    var L = [];

    for (var i = 0; i <= m; i++) {
        L[i] = [];
        for (var j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;

            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;

            else
                L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
        }
    }

    console.log(L[m][n]);
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Common Child Python Solution

s1 = input().strip()
s2 = input().strip()
n = len(s1)
assert n == len(s2)
currow = [0]*(n+1)
#print(len(tbl),[len(row) for row in tbl])
for i in range(n):
    s1i = s1[i]
    prevrow = currow
    currow = [0] 
    cr = 0
    for s2j, nr, nr1 in zip(s2, prevrow, prevrow[1:]):
        if s1i == s2j:
            cr = 1 + nr
        else:
            if cr < nr1:
                cr = nr1
        currow.append(cr)
print(currow[-1])