Hackerrank Common Child Solution
.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;
}