HackerRank Common Child problem solution

In this HackerRank common child interview preparation kit problem solution, A string is said to be a child of 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?

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

HackerRank Common Child problem solution in Python.

import sys

def main():
  a = [l for l in sys.stdin.readline().strip()]
  b = [l for l in sys.stdin.readline().strip()]

  a = [l for l in a if l in b]
  b = [l for l in b if l in a]

  print(len(lcs(a, b)))

def lcs(a, b):
    lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
    # row 0 and column 0 are initialized to 0 already
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                lengths[i+1][j+1] = lengths[i][j] + 1
            else:
                lengths[i+1][j+1] = 
                    max(lengths[i+1][j], lengths[i][j+1])
    # read the substring out from the matrix
    result = ""
    x, y = len(a), len(b)
    while x != 0 and y != 0:
        if lengths[x][y] == lengths[x-1][y]:
            x -= 1
        elif lengths[x][y] == lengths[x][y-1]:
            y -= 1
        else:
            assert a[x-1] == b[y-1]
            result = a[x-1] + result
            x -= 1
            y -= 1
    return result
  
if __name__ == "__main__":
  main()

Common Child problem solution in Java.

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        
        System.out.println(lcs(a,b).length());
    }
    public static String lcs(String str1, String str2)
    {
        int l1 = str1.length();
        int l2 = str2.length();
 
        int[][] arr = new int[l1 + 1][l2 + 1];
 
        for (int i = l1 - 1; i >= 0; i--)
        {
            for (int j = l2 - 1; j >= 0; j--)
            {
                if (str1.charAt(i) == str2.charAt(j))
                    arr[i][j] = arr[i + 1][j + 1] + 1;
                else 
                    arr[i][j] = Math.max(arr[i + 1][j], arr[i][j + 1]);
            }
        }
 
        int i = 0, j = 0;
        StringBuffer sb = new StringBuffer();
        while (i < l1 && j < l2) 
        {
            if (str1.charAt(i) == str2.charAt(j)) 
            {
                sb.append(str1.charAt(i));
                i++;
                j++;
            }
            else if (arr[i + 1][j] >= arr[i][j + 1]) 
                i++;
            else
                j++;
        }
        return sb.toString();
    }
}

Problem solution in C++ programming.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define FOR(a,b,c) for (int a=b,_c=c;a<=_c;a++)
#define FORD(a,b,c) for (int a=b;a>=c;a--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; ++i)
#define REPD(i,a) for(int i=(a)-1; i>=0; --i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(a) int(a.size())
#define reset(a,b) memset(a,b,sizeof(a))
#define oo 1000000007

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn=5007;

int dp[maxn][maxn],n;
char a[maxn],b[maxn];

int main(){
    //freopen("test.txt","r",stdin);
    scanf("%s",a+1);
    scanf("%s",b+1);
    n=strlen(a+1);
    reset(dp,0);
    FOR(i,1,n) FOR(j,1,n){
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    }
    printf("%dn",dp[n][n]);
    return 0;
}

Problem solution in C programming.

#include<stdio.h>
#include<string.h>
int dp[5001][5001];
int main(){
    char st1[5001], st2[5001];
    scanf("%s", st1);
    scanf("%s", st2);
    int m = strlen(st1), n = strlen(st2), i, j;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            if(st1[i-1] == st2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = dp[i][j-1] > dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
    printf("%d", dp[m][n]);
    return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
    var parts = input.split("n"),
        firstStr = parts[0],
        secondStr = parts[1],
        strLen = firstStr.length,
  		arrPrev = new Array(strLen + 1),
        arrCurr = new Array(strLen + 1);
  
  
  	for (var ii = 0; ii <= strLen; ii++) {
      arrPrev[ii] = 0;
      arrCurr[ii] = 0;
    }
  
  	//for (var ii = 0; ii <= strLen; ii++) {
    //  console.log(arrPrev[ii]);
    //}
  	
  	for (ii = 1; ii <= strLen; ii++) {
      for (var jj = 1; jj <= strLen; jj++) {
        if (firstStr[ii - 1] == secondStr[jj - 1]) {
          arrCurr[jj] = arrPrev[jj - 1] + 1;
        }
        else {
          arrCurr[jj] = Math.max(arrCurr[jj - 1], arrPrev[jj]);
        }
      }
      arrPrev = arrCurr.slice(0);
    }
  
  	console.log(arrCurr[strLen]);
}

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

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