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