Skip to content
TheCScience
TheCScience
  • Pages
    • About US
    • Contact US
    • Privacy Policy
    • DMCA
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
TheCScience

HackerRank Common Child Problem Solution

Yashwant Parihar, April 28, 2023May 6, 2023

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

 2

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

0

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

Sample Input 2

SHINCHAN
NOHARAAA

Sample Output 2

3

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

2

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

HackerRank Common Child Problem Solution
HackerRank Common Child Problem Solution

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])            

Other Solutions

  • HackerRank Bear and Steady Gene Solution
  • HackerRank Morgan and a String Problem Solution
c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython

Post navigation

Previous post
Next post

Leave a Reply

You must be logged in to post a comment.

Similar websites

  • Programming
  • Data Structures
©2025 TheCScience | WordPress Theme by SuperbThemes