HackerRank Common Child problem solution YASH PAL, 31 July 202410 September 2024 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); }); coding problems interview prepration kit