HackerRank Common Child problem solution

In this HackerRank common child interview preparation kit problem you have Given two strings of equal length, what’s the longest string that can be constructed such that it is a child of both?

Problem solution in Python programming.

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

Problem solution in Java Programming.

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);
});