You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Hackerrank Common Child Solution

Hackerrank Common Child Solution

Beeze Aal
Beeze Aal

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.  Given two strings of equal length, what's the longest string  that can be constructed such that it is a child of both?

For example, ABCD and ABDC have two children with maximum length 3, ABC and ABD.  They can be formed by eliminating either the D or C from both strings.  Note that we will not consider ABCD as a common child because we can't rearrange characters and ABCD  ABDC.

Function Description

Complete the commonChild function in the editor below.  It should return the longest string which is a common child of the input strings.

commonChild has the following parameter(s):

  • s1, s2:  two equal length strings

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

There is one line with two space-separated strings,  and .

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

  • All characters are upper case in the range ascii[A-Z].

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Print the length of the longest string , such that  is a child of both  and .

Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

HARRY
SALLY

Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

 2

Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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

Sample Input 1

AA
BB

Sample Output 1

0

Explanation 1

and  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  and  while maintaining the order is .

Sample Input 3

ABCDEF
FBDAMN

Sample Output 3

2

Explanation 3
is the longest child of the given strings.

Solution in java8

Approach 1.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the commonChild function below.
    static int commonChild(String s1, String s2) {
        int length1= s1.length(), length2= s2.length();
        int[][] lcs = new int[length1+1][length2+1];
        for(int i=-1;++i<=length1;){
            for(int j=-1;++j<=length2;){
                if(i==0||j==0)
                    lcs[i][j]=0;
                else if(s1.charAt(i-1)==s2.charAt(j-1))
                    lcs[i][j]= lcs[i-1][j-1]+1;
                else
                    lcs[i][j]=Math.max(lcs[i-1][j],lcs[i][j-1]);    
            }
        }
        return lcs[length1][length2];
    }

    private static final Scanner scanner = new Scanner(System.in);

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

        String s1 = scanner.nextLine();

        String s2 = scanner.nextLine();

        int result = commonChild(s1, s2);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Approach 2.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the commonChild function below.
    static int commonChild(String s1, String s2) {
    int[][] C = new int[s1.length()+1][s2.length()+1];

        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.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 < s1.length(); i++) {
        }

        return C[s1.length()][s2.length()];

    }

    private static final Scanner scanner = new Scanner(System.in);

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

        String s1 = scanner.nextLine();

        String s2 = scanner.nextLine();

        int result = commonChild(s1, s2);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Approach 3.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the commonChild function below.
    static int commonChild(String a, String b) {

        //int len = a.length();
        
        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()];
        
        

    }

    private static final Scanner scanner = new Scanner(System.in);

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

        String s1 = scanner.nextLine();

        String s2 = scanner.nextLine();

        int result = commonChild(s1, s2);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Solution in python3

Approach 1.

s1 = list(input())
s2 = list(input())

n = len(s1)
m = len(s2)

l = [[0]*(n+1) for i in range(m+1)]
for i in range(n):
    for j in range(m):
        if s1[i] == s2[j]:
            l[i + 1][j + 1] = l[i][j] + 1
        else:
            l[i + 1][j + 1] = max(l[i + 1][j], l[i][j + 1])

print(l[-1][-1])


Approach 2.

#!/bin/python

import math
import os
import random
import re
import sys

# Complete the commonChild function below.
def commonChild(s1, s2):
    prev_child = [0] * (len(s2) + 1)
    curr_child = [0] * (len(s2) + 1)
    for c1 in s1:
        curr_child, prev_child = prev_child, curr_child
        for j, c2 in enumerate(s2, 1):
            curr_child[j] = (
                1 + prev_child[j - 1] if c1 == c2 else
                max(prev_child[j], curr_child[j - 1])
            )
    return curr_child[-1]
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s1 = raw_input()

    s2 = raw_input()

    result = commonChild(s1, s2)

    fptr.write(str(result) + '\n')

    fptr.close()

Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the commonChild function below.
def commonChild(s1, s2):
    n = len(s1)
    lcs = [[0]*(n+1) for _ in range(2)]


    for i in range(1, n+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                lcs[1][j] = lcs[0][j-1] + 1
            else:
                if lcs[0][j] >= lcs[1][j-1]:
                    lcs[1][j] = lcs[0][j]
                else:
                    lcs[1][j] = lcs[1][j-1]

        lcs[0] = lcs[1][:]

    return lcs[0][n]
            


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s1 = input()

    s2 = input()

    result = commonChild(s1, s2)

    fptr.write(str(result) + '\n')

    fptr.close()

Solution in cpp

Approach 1.

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


int main() {
    string A, B; cin >> A >> B;
    int la = A.size(), lb = B.size();
    vector<vector<int>> dp(la + 1, vector<int>(lb + 1));
    for (int ia = 1; ia <= la; ia++) {
        for (int ib = 1; ib <= lb; ib++) {
            if (A[ia - 1] == B[ib - 1]) dp[ia][ib] = dp[ia - 1][ib - 1] + 1;
            else dp[ia][ib] = max(dp[ia - 1][ib], dp[ia][ib - 1]);
        }
    }
    cout << dp.back().back() << endl;
    return 0;
}

Approach 2.

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


int main() {
    string A, B;
    cin >> A >> B;
    int a = A.length();
    int b = B.length();
    vector<vector<int>> arr(a+1, vector<int>(b+1, 1000000000));
    for (int y = 0; y < b; ++y) arr[0][y] = y;
	for (int x = 0; x < a; ++x) arr[x][0] = x;

    for (int y = 0; y < b; ++y) {
    	arr[0][y] = y;
    	for (int x = 0; x < a; ++x) {
    		arr[x][0] = x;
    		arr[x+1][y+1] = min(arr[x][y+1]+1, arr[x+1][y]+1);
    		if(A[x] == B[y]){
    			arr[x+1][y+1] = min(arr[x][y], arr[x+1][y+1]);
    		}
    		// cout << arr[x+1][y+1] << ' ' ;
    	}
    	// cout << endl;
    }
    cout << (a+b-arr[a][b])/2 << endl;

    return 0;
}

Approach 3.

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

int lcs(string &a, string &b) {
    int m = a.length() + 1;
    int n = b.length() + 1;
    int** cache = new int*[m];
    for (int i = 0; i < m; i++) {
        cache[i] = new int[n];
        for (int j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
                cache[i][j] = 0;
            } else if (a.at(i - 1) == b.at(j - 1)) {
                cache[i][j] = cache[i - 1][j - 1] + 1;
            } else {
                cache[i][j] = max(cache[i][j - 1],  cache[i - 1][j]);
            }
        }
    }
    return cache[a.length()][b.length()];
}

int main() {
    string a, b;
    cin >> a;
    cin >> b;
    printf("%d\n", lcs(a, b));
    return 0;
}